RÉSOLUTION DE PROGRAMMES LINÉAIRES ENTIERS OU MIXTES À L'AIDE DE LA FORME NORMALE DE HERMITE

摘要

Integer Linear Programming (ILP) is especially hard when the solutions of its integral relaxation are far from its true solutions. Such a situation is in some way related to the geometrical properties of the associated polyedron. We present here an approach for ILP which is based upon a systematical use of specific changes of variables. These changes of variables involve Hermite Normal Form decompositions and allow the implementation of specific cutting plane methods and branch and bound methods. We describe and test these methods, and conclude this work by introducing several open problems.%Un programme linéaire entier ou mixte s'avère en pratique d'autant plus difficile à résoudre que les solutions de la relaxation entière de ce programme sont susceptibles d'être éloignées des véritables solutions du système. Une telle situation tend à se produire quand les angles coniques définis par les sommets du polyèdre sous-jacent au programme relâché sont très aigus ou plats (proches de 0 modulo Π). Nous présentons ici une approche pour le traitement de tels programmes qui est basée sur l'utilisation de changements de variables permettant de régulariser localement ce polyèdre et de faire apparaître de façon naturelle des candidats à la solution. Nous en déduisons différentes interprétations algorithmiques, par génération de coupes et sauts aléatoires, par séparation et évaluation, par décomposition de Benders, dont nous vérifions la convergence et testons l'efficacité.