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.
| Subject : | : | typdoc_1455 |
| Language of text | : | French |
| Topics | : | Non-linear optimisation, bi-level optimisation and yield management |
| Keywords | : | Programmation semi ; définie ; problème de l'affectation quadratique QAP ; relaxations ; algorithmes de séparation et évaluation ; grille de calcul. |
| PDF version | : |  PDF version |
