Branch-and-cut bi-objectif appliqué au problème du sac-à-dos bi-dimensionnel

Session : SS2-4 / SS2 : Application et théorie de l’optimisation multiobjectif
Vendredi 12 février 10:30 - 11:50 Salle : RP8
Audrey Cerqueus, Xavier Gandibleux, Anthony Przybylski, Frédéric Saubion et Stefan Ruzika

Ce travail porte sur la résolution exacte du problème de sac-à-dos bi-objectif bi-dimensionnel, en utilisant un algorithme de branch-and-cut. Cet algorithme associe les idées des méthodes de plans coupants et de l’algorithme du branch-and-bound. L’algorithme de branch-and-bound (aussi appelé procédure de séparation et évaluation) repose, comme son nom l’indique, sur l’évaluation de sous-problèmes. La relaxation convexe s’est montrée efficace en pratique pour l’évaluation de sous-problèmes pour plusieurs problèmes bi-objectif, mais est coûteuse pour le problème du sac-à-dos bi-objectif bi-dimensionnel. La relaxation continue peut être résolue, relativement facilement, par l’algorithme du simplexe paramétrique, mais l’ensemble bornant supérieur obtenu est considérablement moins serré. Par conséquent, lorsque cette relaxation est utilisée, les arbres de recherche sont généralement grands. Le but de ce travail est d’améliorer la qualité de l’ensemble bornant supérieur obtenu par la relaxation continue, en introduisant des inégalités de couverture, à chaque nœud de l’algorithme de branch-and-bound. L’algorithme devient donc un branch-and-cut. Nous comparons les performances obtenues considérant plusieurs variantes des inégalités de couverture, telles que les couverture étendues et les couvertures augmentées (lifted cover inequalities en anglais). La méthode est validées expérimentalement.

Mots clés : Branch-and-cut, optimisation combinatoire multi-objectif, problème du sac-à-dos