Introduction
La programmation linéaire en nombres entiers est l'une des techniques classiques qui ont été largement utilisées dans la résolution des problèmes d'optimisation combinatoire. Elle peut être vue comme un cas particulier de la procédure de séparation et d'évaluation dont l'évaluation est basée sur une relaxation de la contrainte des variables entières dans le problème initial. Cette relaxation conduit à considérer des variables continues dans chaque branche au lieu des variables de décision entières. La détermination de la borne (en phase d'évaluation) peut être facilement effectuée par la résolution d'un programme linéaire à variables continues. Cette résolution, qui est polynomiale, se repose sur les travaux de Simplexe et sur les algorithmes des points intérieurs de Karamarkar [Wolsey, 1998]. Elle consiste à minimiser une fonction coût en respectant des contraintes. Le critère et les contraintes sont des fonctions linéaires des variables du problème.
D'autres variantes plus avancées ont vu le jours et constituent un ensemble parmi les méthodes les plus efficaces dans le domaine de l'optimisation combinatoire. Elles s'inscrivent aujourd'hui dans un thème important qui est la Programmation Mathématique. Parmi ces variantes, on peut citer les méthodes de Branch-and-Cut, de Branch-and-Price et de l'analyse faciale [Mahjoub 2005].
