Encadrant: Pierre Fouilhoux, LIP6, Equipe Recherche Opérationnelle
Sujet destiné à un binôme
<strong>Pré-requis:</strong>
Connaissances en algorithmique et programmation linéaire
Goût pour la programmation (langage C, C++, java)
Goût pour l'étude théorique de problème combinatoire
<strong> Cadre: </strong>
Pour résoudre un problème d'optimisation combinatoire NP-difficile, le seul cadre générique de résolution existant est celui de la méthode de branchement et évaluation (Branch-and-Bound). Cette méthode est la base des logiciels ``solveurs'' (``MIP solver'') qui permettent de résoudre des programmes linéaires en nombres entiers (MIP, Mixed Integer Programming). Comme la programmation linéaire est un outil pratique pour la modélisation de problème d'optimisation combinatoire, ces solveurs sont fréquemment utilisés en pratique.
Beaucoup d'améliorations théoriques et pratiques ont permis à ces solveurs de devenir de plus en plus performants (prétraitements basés sur l'inférence logique, ajouts d'inégalités valides, renforcement d'inégalités,...). Ainsi résoudre par exemple le problème du sac-à-dos entiers est possible pour de très grandes tailles d'instances en utilisant ces solveurs (Cplex, Gurobi, Scip,...).
Toutefois il existe bien-entendu des instances difficiles, même pour le problème du sac-à-dos. Ces instances difficiles possèdent fréquemment un espace de solutions avec de fortes symétries. On dit que deux vecteurs-solutions du problème sont symétriques si l'on peut passer de l'un à l'autre en permutant des coefficients et que leur coût est identique. Ainsi, de telles symétries empêchent d'élaguer des solutions car toutes les solutions symétriques doivent être explorées et les arborescences issues de la méthode de Branch-and-Bound explosent en taille et en temps d'exploration nécessaire.
Il existe plusieurs méthodes pour prendre en compte des instances à forte symétrie. L'une d'entre elles repose sur une reformulation du problème permettant de n'explorer qu'une solution par classe d'équivalence de ces symétries. Pour cela, on doit mettre en place un branchement particulier, dit branchement orbital, ou ajouter des inégalités particulières.
<strong>Travail à effectuer:</strong>
Dans ce projet, nous nous intéresserons en particulier au problème du sac-à-dos. Nous construirons des instances qui sont difficiles à résoudre pour les logiciels solveurs et nous tenterons de déterminer leurs quantités de solutions symétriques.
Le but du projet est de mettre en oeuvre plusieurs idées de branchement dans le but d'améliorer les performances des logiciels solveurs. Pour cela, nous changerons les méthodes de branchements d'un de ces solveurs et testerons expérimentalement l'efficacité résultante.
Suivant les résultats obtenus, nous pourrons nous orienter vers l'intégration d'idées provenant de la littérature (dominance des espaces de solutions, contraintes orbitopales,...) ou poursuivre les tests expérimentaux sur d'autres problèmes (problème de bin-packing, problème de l'UCP,...).
Contact: pierre.fouilhoux@lip6.fr