Simplexe en nombres entiers avec décomposition

 

Issmail Elhallaoui

École Polytechnique Montréal

 

Domaine : structures abstraites

Programme établissement de nouveaux chercheurs universitaires

Concours 2012-2013

Dans ce projet de recherche, nous introduisons une nouvelle approche pour résoudre en nombres entiers les problèmes de partitionnement. Cette approche apporte une réponse intéressante à une question ouverte depuis plusieurs dizaines d'années: comment passer d'une solution entière à une autre solution entière sans devenir fractionnaire tout en minimisant le coût de l'objectif? Plusieurs variantes de l'algorithme du simplexe en nombre entiers ont tenté par le passé d'y répondre en faisant des pivots de simplexe. Ces algorithmes présentent deux inconvénients majeurs : soit ils se bloquent dans des minimums locaux, soit les solutions de base deviennent fractionnaires.

En plus d'une preuve théorique, la réponse apportée par ce projet de recherche a un caractère pratique précisant comment remédier aux faiblesses citées en haut. Pour faire le saut entre deux solutions de base entières voisines, nous résolvons un problème complémentaire, beaucoup plus facile que le problème original, afin d'identifier un ou plusieurs variables à ajouter dans la base. Commençant par une solution entière initiale heuristique, notre approche préserve l'intégralité de la solution à chaque itération. La méthode proposée a un grand potentiel d'application dans le domaine de transport où beaucoup de problèmes sont modélisés comme des problèmes de type partitionnement, généralement de très grande taille. Elle est particulièrement très utile pour la ré-optimisation en cas de perturbation.