Recherche opérationnelle
La programmation en nombres entiers
- Présentation du cours
- Qu'est-ce que la recherche opérationnelle
- Modéliser un problème de décision
- Le programme linéaire et ses formes
- La résolution graphique
- Le simplexe, la méthode
- Le simplexe, les cas particuliers
- La dualité
- L'analyse de sensibilité
- Le problème de transport
- Le problème d'affectation
- Les graphes, vocabulaire et représentation
- Le plus court chemin
- Le flot maximal
- L'ordonnancement de projet
- La programmation en nombres entiers
- Gestion des stocks et files d'attente
Recherche opérationnelle
Chapitre 14 : La programmation en nombres entiers
Arrondir ne suffit pas
Le problème
Le programme en nombres entiers
\max \; \mathbf{c}'\mathbf{x} \qquad \text{sous} \qquad \mathbf{Ax} \leq \mathbf{b}, \quad \mathbf{x} \geq \mathbf{0}, \quad \mathbf{x} \in \mathbb{Z}^n
Un exemple à deux variables
\max \; Z = 5x + 4y \qquad \begin{cases} 6x + 4y \leq 24\\ \phantom{6}x + 2y \leq \phantom{0}6 \end{cases}
La solution continue
La relaxation linéaire
Les deux contraintes se croisent en x = 3, y = 1{,}5, pour
Z = 15 + 6 = 21
Trois raisons de ne pas arrondir
Arrondir vers le bas donne (3,1), admissible, Z = 19 — mais l’optimum entier vaut 20.
Arrondir vers le haut donne (3,2), qui viole x + 2y \leq 6.
À plus de deux variables, le point arrondi peut être très loin de l’optimum entier, voire hors du domaine.
Ce que la relaxation apporte tout de même
Une borne, et elle est précieuse
Le domaine entier est inclus dans le domaine continu. Donc
Z_{\text{entier}}^* \;\leq\; Z_{\text{continu}}^* = 21
C’est tout l’algorithme en germe
Si l’on trouve une solution entière valant 20 et qu’une branche de l’exploration a une borne de 18, on peut abandonner cette branche sans l’explorer.
C’est la séparation et l’évaluation.
Séparation et évaluation
Le principe
Branch and bound
Séparer — choisir une variable fractionnaire x_j = v et créer deux sous-problèmes : x_j \leq \lfloor v \rfloor et x_j \geq \lceil v \rceil.
Évaluer — résoudre la relaxation de chaque sous-problème pour obtenir sa borne.
Élaguer — abandonner une branche dont la borne ne dépasse pas la meilleure solution entière connue.
Ce que la séparation ne perd pas
Aucune solution entière n’est éliminée : entre \lfloor v \rfloor et \lceil v \rceil, il n’y a pas d’entier.
On coupe le domaine continu sans toucher aux points entiers.
L’arbre de recherche
Le déroulement
Nœud racine, puis séparation sur y
Racine : x = 3, y = 1{,}5, borne 21. On sépare sur y.
Branche y \leq 1 : x = 3{,}33, y = 1, borne 20{,}67.
Branche y \geq 2 : x = 2, y = 2, Z = 18. Solution entière, mais faible.
On sépare la première branche sur x
y \leq 1 et x \leq 3 : x = 3, y = 1, Z = 19. Entière.
y \leq 1 et x \geq 4 : x = 4, y = 0, Z = \mathbf{20}. Entière, et meilleure.
La conclusion
L’optimum entier
x = 4, \qquad y = 0, \qquad Z = 20
Ce que l’élagage a économisé
La branche y \geq 2 avait une borne de 18, inférieure à la meilleure solution entière trouvée : on ne l’a pas explorée plus avant.
Sur un problème à cent variables binaires, l’énumération complète exigerait 2^{100} essais. L’élagage ramène cela à quelques milliers.
Les variables binaires
Ce qu’elles permettent de modéliser
Trois usages
Le choix — x = 1 si l’on ouvre l’usine, 0 sinon.
Le coût fixe — x \leq M\delta : produire oblige à payer le coût fixe attaché à \delta.
L’exclusion — \delta_1 + \delta_2 \leq 1 : au plus un des deux projets.
Le coût fixe, en détail
\max \; 30x - 5\,000\,\delta \qquad \text{sous} \qquad x \leq 10\,000\,\delta, \quad \delta \in \{0,1\}
Si x > 0 alors \delta = 1, donc le coût fixe est payé. Si x = 0, on peut prendre \delta = 0.
Le rôle de la grande constante
M doit être assez grand pour ne jamais borner x à tort, et assez petit pour que la relaxation reste informative.
Un M démesuré donne une borne si lâche que l’élagage ne coupe plus rien : le calcul explose.
Les coupes
L’autre grande famille
Gomory, 1958
Au lieu de séparer, on ajoute une contrainte qui élimine la solution fractionnaire courante sans éliminer aucun point entier.
On résout à nouveau, et l’on recommence jusqu’à tomber sur une solution entière.
Ce que font les solveurs actuels
Ils combinent les deux : branch and cut. Des coupes resserrent la relaxation à chaque nœud, ce qui améliore les bornes, ce qui élague davantage.
Un problème à dix mille variables binaires se résout aujourd’hui en quelques minutes — c’était impensable il y a trente ans.
Ce qu’il faut retenir
Le résumé du chapitre
Six points
- Arrondir la solution continue ne donne pas l’optimum entier, et peut sortir du domaine.
- La relaxation fournit néanmoins une borne supérieure : 21 ici.
- Séparer sur une variable fractionnaire ne perd aucun point entier.
- Élaguer abandonne toute branche dont la borne n’atteint pas la meilleure solution connue.
- Sur l’exemple : optimum entier x = 4, y = 0, Z = 20 — et non (3,1) à 19.
- Les variables binaires modélisent choix, coûts fixes et exclusions.
La suite
Le chapitre 15 clôt le cours sur deux problèmes où le temps entre en jeu : combien commander à la fois, et combien de guichets ouvrir.
Ressources du chapitre
- Diapositives
- Polycopié du chapitre
- Exercices corrigés
- Application interactive
- — Vidéo
- QCM (bientôt)