Le problème d’affectation quadratique a été proposé à la fin des années 50 pour modéliser des problèmes de localisation d’activités. Il est emblématique de la classe des problèmes NP-difficiles, tandis que le problème d’affectation linéaire est lui bien résolu en temps polynomial. Nous montrons comment ce problème peut se modéliser comme un réseau de fonctions de coûts. Pour mieux le résoudre, nous avons développé de nouvelles contraintes globales (AllDifferent, GlobalCardinalityConstraint) et mis en oeuvre des algorithmes de reformulation efficaces issus de la théorie des graphes et de la programmation mathématique. Des résultats expérimentaux comparant différentes approches exactes et inexactes seront présentées.
Guidio Sewa, David Allouche, Simon de Givry, George Katsirelos, and Thomas Schiex,
Singleton Node Consistency for Quadratic Assignment Problems,
In Proc. of CPAIOR-26, Rabat, Morocco, 2026
Guidio Sewa, David Allouche, Simon de Givry, George Katsirelos, Pierre Montalbano, and Thomas Schiex, Assignment problems in cost function networks, In Proc. of AAAI-26, Singapore, 2026