Voir la source de Optimisation linéaire en nombres entiers

{{Voir homonymes|ILP}}

L''''optimisation linéaire en nombres entiers''' (OLNE) (ou '''programmation linéaire en nombres entiers''' (PLNE) ou '''{{langue|en|integer programming}}''' (IP) ou '''Integer Linear Programming''' (ILP)) est un domaine des [[mathématiques]] et de l'[[informatique théorique]] dans lequel on considère des problèmes d'[[optimisation (mathématiques)|optimisation]] d'une forme particulière. Ces problèmes sont décrits par une fonction de coût et des contraintes linéaires, et par des variables entières. 

La contrainte d'intégralité sur les variables, qui différencie l'OLNE de l'[[optimisation linéaire|optimisation linéaire classique]] est nécessaire pour modéliser certains problèmes, en particulier des problèmes algorithmiques. Mais cette contrainte supplémentaire rend le problème plus complexe et demande des techniques particulières.

== Définitions ==

=== Définitions générales ===

Un problème d'optimisation est un [[problème algorithmique|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 [[combinaison linéaire|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''.

=== Formes canonique et standard ===

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 :

:<math> \begin{align}
& \text{maximiser}   && \mathbf{c}^\mathrm{T} \mathbf{x}\\
& \text{tel que} && A \mathbf{x} \le \mathbf{b}, \\
&  && \mathbf{x} \ge \mathbf{0}, \\
& \text{et} && \mathbf{x} \in \mathbb{Z},
\end{align} </math>,

et la forme standard est :

:<math> \begin{align}
& \text{maximiser}   && \mathbf{c}^\mathrm{T} \mathbf{x}\\
& \text{tel que} && A \mathbf{x} + \mathbf{s} = \mathbf{b}, \\
&  && \mathbf{s} \ge \mathbf{0}, \\
&  && \mathbf{x} \ge \mathbf{0}, \\
& \text{et} && \mathbf{x} \in \mathbb{Z},
\end{align} </math>

où <math>\mathbf{c}, \mathbf{b}</math> sont des vecteurs et <math>A</math> est une matrice ayant des valeurs entières.

== Exemple ==

[[File:IP polytope with LP relaxation.png|350px|thumb|Problème d'OLNE et relaxation linéaire]]
On donne un exemple de problème d'OLNE, illustré par l'image ci-contre.
:<math>
     \begin{align}
      \max  & \text{ } y \\
            -x +y & \leq 1  \\
            3x +2y & \leq 12 \\
            2x +3y & \leq 12 \\
            x,y & \ge 0 \\
            x,y & \in \mathbb{Z}
     \end{align}
</math>

Il y a deux variables, les solutions sont donc des couples d'entiers. Les points rouges sont les couples qui vérifient les contraintes et les pointillés rouges montrent l'[[enveloppe convexe]] de ces points. Les solutions optimales de ce problème sont (1,2) et (2,2).

Les lignes bleues et les axes des abscisses et des ordonnées délimitent les couples de réels qui satisfont toutes les contraintes sauf la contrainte d'intégralité. L'optimum est meilleur dans cette version relaxée.

== Modélisation par OLNE ==

De nombreux problèmes de [[recherche opérationnelle]] et d'[[algorithmique]] peuvent être traduits en problème d'OLNE. Par exemple le [[problème de couverture par ensembles]] est le suivant. Étant donné un [[ensemble]] ''A'', on dit qu'un élément ''e'' est couvert par ''A'' si ''e'' appartient à ''A'' ; pour un ensemble ''U'' et une famille ''S'' de sous-ensembles de ''U'', le problème consiste à couvrir tous les éléments ''U'' avec une sous-famille de ''S'' la plus petite possible. Ce problème se traduit naturellement sous la forme suivante<ref>Voir par exemple {{lien web|langue=en |url=http://mat.gsia.cmu.edu/orclass/integer/node8.html#SECTION00034000000000000000|titre= A Tutorial on Integer Programming : Set Covering|date= 1997 | auteur =Michael A. Trick}}</ref> : 

<center>
{|
| minimiser : 
| <math>\sum_{S \in \mathcal S}x_S</math>
|
| (Minimiser le nombre de sous-ensembles)
|-
| tel que : 
| <math>\sum_{S\colon e \in S} x_S \geqslant 1 </math>
| <math>\forall e\in \mathcal U</math>
| (Tous les éléments sont couverts)
|-
|
| <math>x_S \in \{0,1\}</math>
| <math>\forall S\in \mathcal S</math>.
| (Chaque sous-ensemble est, ou bien dans la couverture, ou bien pas)
|}
</center>

== Résolution ==

=== Complexité ===

Au sens de la [[théorie de la complexité (informatique théorique)|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]]<ref>Il fait d'ailleurs partie de la liste des [[21 problèmes NP-complets de Karp]] sous le nom de ''0-1 INTEGER PROGRAMMING''. Voir : {{Reducibility Karp 1972}}.</ref>. 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 [[Hendrik_Lenstra|Lenstra]] en 1983 <ref>{{Article |langue=en |auteur1=H. W. Lenstra |titre=Integer programming with a fixed number of variables |périodique=Mathematics of operations research |date=1983 |lire en ligne=https://openaccess.leidenuniv.nl/bitstream/handle/1887/3806/346_046.pdf?sequence=1 }}</ref>.

=== Cas particuliers ===

Lorsque les contraintes prennent la forme d'une [[Matrice_unimodulaire#Matrice_totalement_unimodulaire|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<ref>
{{article
 |auteur =[[Hendrik Lenstra]]
 |titre= Integer programming with a fixed number of variables
 |journal= Mathematics of operations research
 |volume= 8|numéro= 8|date= November 1983}}.</ref>.

=== Méthodes de résolution exacte ===

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]] (''{{langue|en|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|''{{langue|en|branch and cut}}'']] <ref>{{Article |langue=anglais |auteur1=Gérard Cornuéjols |titre=The Ongoing Story of Gomory Cuts |périodique=Documenta Math |date=2012 |lire en ligne=https://www.math.uni-bielefeld.de/documenta/vol-ismp/37_cornuejols-gerard.pdf }}</ref>.

=== Approximation ===

La théorie des [[algorithme d'approximation|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 [[complexité en temps|temps polynomial]]{{refnec}}.

== Applications ==
Ce type d'optimisation est très utilisée en [[recherche opérationnelle]]. C'est aussi devenu une approche classique en [[bio-informatique]]<ref>{{site web|url=https://simons.berkeley.edu/events/integer-linear-programming-in-computational-biology|titre=Integer Linear Programming in Computational Biology (symposium)|site={{lien|Simons Institute for the Theory of Computing}}}}.</ref>{{,}}<ref>{{lien web|url=http://csiflabs.cs.ucdavis.edu/~gusfield/tutorial.pdf|titre=Integer Linear Programming in Computational Biology tutorial|auteur=[[Dan Gusfield]]|date=juin 2017}}.</ref>.

== Notes et références ==
{{Traduction/Référence|en|Integer programming|628140390}}
<references />

== Bibliographie ==

* {{chapitre
 |langue = en
 |auteur = Bradley, Hax, and Magnanti
 |titre ouvrage = Applied Mathematical Programming
 |titre chapitre = Integer programming
 |éditeur = Addison-Wesley
 |année = 1977}}

== Lien externe ==

* {{Lien web|langue=fr |url=http://www.lix.polytechnique.fr/~liberti/teaching/isic/isc612-07/ip.pdf |titre=Présentation : Introduction à la Programmation
Linéaire en Nombres Entiers |date= 2006|site= École polytechnique | auteur = Leo Liberti et Ruslan Sadykov}}
{{Palette|Optimisation}}
{{Portail|mathématiques|informatique théorique}}

[[Catégorie:Informatique théorique]]
[[Catégorie:Optimisation combinatoire]]
[[Catégorie:Problème NP-complet]]