Program > By author > Lehireche Ahmed

Wednesday 26
Non-linear optimisation, bi-level optimisation and yield management
Serigne Gueye
› 10:30 - 11:00 (30min)
› Bât. A - TD 34
Résolution Exacte du Problème d'Affectation Quadratique en utilisant des relaxations Semi Définies Positives.
Orkia Derkaoui  1@  , Ahmed Lehireche  2@  
1 : Université Dr Moulay Tahar de Saida, Département d'Informatique  -  Website
BP 138 cité ENNASR, Saida 20000 -  Algérie
2 : Université Djillali Liabes de Sidi Bel Abbes, Departement d'Informatique  -  Website
BP 89 Sidi Bel Abbes 22000 -  Algérie

Le problème d'affectation quadratique (QAP) est un problème d'optimisation combinatoire NP-difficile très connu. Sa résolution est importante car beaucoup de problèmes industriels sont modélisés par ce modèle et de nombreux autres problèmes d'optimisation combinatoire, comme le problème du voyageur de commerce (TSP), ou encore des problèmes de la théorie de graphe tels le problème de clique maximal et le problème de partitionnement de graphe s'expriment comme des cas particuliers du QAP.

Nous mettons en œuvre la résolution exacte du QAP avec la méthode Branch-and-Bound. Pour augmenter la performance de cette méthode, nous utilisons la relaxation Semi Définie Positive (SDP) du QAP afin d'obtenir une borne de bonne qualité. Nous utilisons dans nos travaux deux solveurs: SDPA (SemiDefinite Programming Algorithm) et SB (Spectral Bundle method). Pour les tests expérimentaux, nous utilisons la librairie QAPLIB. Comme perspective, nous jugeons que l'exploitation de la puissance de calcul comme celle des grappes et grilles de machines peut remédier au coût en temps de calcul des relaxations SDP.


Online user: 1