Optimisation linéaire en nombres entiers

Un problème d'optimisation est un problème mathématique où, étant donné un ensemble de variables et des contraintes sur ces variables, on doit trouver une assignation qui maximise (ou minimise) une certaine fonction de coût. On parle de problème linéaire lorsque les contraintes et la fonction de coût sont combinaisons linéaires des variables et le problème est à nombres entiers si ces variables ne sont autorisées qu'à prendre des valeurs dans l'ensemble des entiers.

La contrainte qui force les variables à prendre des valeurs entières est appelée contrainte d'intégralité. Lorsque l'on gomme cette contrainte, on parle d'un problème relaxé ou de relaxation continue, et l'on a alors affaire à un problème d'optimisation linéaire. Le rapport entre l'optimal dans la version relaxée et dans la version entière est souvent appelé integrality gap.

Un problème d'OLNE peut être mis sous deux formes classiques : la forme canonique et la forme standard. La forme canonique pour une maximisation est :

${\displaystyle {\begin{aligned}&{\text{maximiser}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{tel que}}&&A\mathbf {x} \leq \mathbf {b} ,\\&&&\mathbf {x} \geq \mathbf {0} ,\\&{\text{et}}&&\mathbf {x} \in \mathbb {Z} ,\end{aligned}}}$,

et la forme standard est :

${\displaystyle {\begin{aligned}&{\text{maximiser}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{tel que}}&&A\mathbf {x} +\mathbf {s} =\mathbf {b} ,\\&&&\mathbf {s} \geq \mathbf {0} ,\\&&&\mathbf {x} \geq \mathbf {0} ,\\&{\text{et}}&&\mathbf {x} \in \mathbb {Z} ,\end{aligned}}}$

où ${\displaystyle \mathbf {c} ,\mathbf {b} }$ sont des vecteurs et ${\displaystyle A}$ est une matrice ayant des valeurs entières.

Au sens de la théorie de la complexité, l'optimisation linéaire en nombres entiers est considérée comme difficile car c'est un problème NP-difficile[2]. Cette complexité est facilement déduite de la NP-difficulté du problème de couverture par ensembles. Une des conséquences pratiques est que, pour des problèmes de grande taille, le temps de calcul peut être très grand.

Cependant, la complexité est polynomiale quand le nombre de variables est fixé, comme montré par Lenstra en 1983 [3].

Lorsque les contraintes prennent la forme d'une matrice totalement unimodulaire et entière, une résolution en temps polynomial est possible car les solutions du problème relaxé sont entières.

Si le nombre de variables est fixé, alors le problème est aussi polynomial[4].

Parmi les méthodes classiques de résolution, on peut citer la méthode des plans sécants (notamment à l'aide de coupes de Gomory) et le principe de séparation et évaluation (branch and bound). Depuis les années 1990, l'inclusion de coupes de Gomory a permis de grandement accélérer l'algorithme séparation et évaluation. Cela a donné naissance à une nouvelle classe d'algorithmes nommés branch and cut [5].

La théorie des algorithmes d'approximation fait souvent appel à une formulation OLNE des problèmes et essaie de borner l'integrality gap pour obtenir une solution approchée en temps polynomial^{[réf. nécessaire]}.