Groupe d’études et de recherche en analyse des décisions

G-2014-14

Valid inequalities and separation algorithms for the set partitioning problem

, et

Dans cet article, nous étudions des stratégies pour résoudre le problème de partitionnement d'ensemble (PPE), en particulier les gains en efficacité qui peuvent être obtenus grâce à des plans de coupure basés sur des inégalités de Chvátal-Gomory de rang 1 et des inégalités de cliques. Nous montrons que pour beaucoup d'exemplaires du PPE, l'introduction de certains de ces plans de coupure dans la formulation standard du PPE permet à un logiciel commercial tel que CPLEX de calculer plus rapidement des solutions optimales.

, 17 pages

Ce cahier a été révisé en juillet 2015