Recherche opérationnelle

Programmation en nombres entiers et variables binaires

On n'achète pas 3,7 camions, et on n'ouvre pas à moitié une usine. Ce simple fait change tout : le problème devient bien plus difficile, mais il permet aussi d'exprimer des choix par oui ou non. Comment écrire ces décisions, et comment les résoudre sans tout essayer ?

Un programme en nombres entiers est un programme linéaire auquel on ajoute une exigence : certaines variables doivent être entières. Sur le papier, c'est peu de chose ; en réalité, on perd la belle méthode du simplexe, car l'optimum n'est plus sur un sommet. En retirant cette exigence, on obtient la relaxation du problème : un problème plus facile, qui donne toujours une borne sur la réponse.

La séparation et l'évaluation en direct : le domaine se découpe, et les deux bornes de la solution se rapprochent jusqu'à se rejoindre.

Tous les exemples sont inventés pour rester lisibles. Les résultats sont calculés sur place dans votre navigateur et confrontés à une seconde méthode, en général l'examen de toutes les possibilités.

Planche 1

Décisions entières : pourquoi ne pas simplement arrondir ?

Une variable entière compte des objets indivisibles : véhicules, machines, personnes. La tentation est forte : résoudre sans se soucier des entiers, puis arrondir. Essayez sur trois situations.

Zone bleue : la relaxation. Points : les décisions entières admissibles. Croix violette : optimum relâché. Rond orange : arrondi au plus proche. Carré vert : arrondi « prudent ». Point rouge : le vrai optimum entier.

Valeur optimale selon la donnée du curseur. Courbe lisse : la relaxation. Escalier : le vrai problème en entiers. L'écart entre les deux varie sans cesse, et ne se prévoit pas.

Optimum relâché–

Arrondi au plus proche–

Arrondi prudent–

Vrai optimum entier–

Écart d'intégrité (relaxation contre entier)–

Sur 2 000 problèmes au hasard : arrondi proche interdit–

Arrondi vers le bas : optimal dans–

Perte moyenne de l'arrondi vers le bas–

Ce qu'il faut retenir. Arrondir peut donner un plan interdit, ou un plan admissible loin du meilleur. Sur le cas des machines avec un budget de 13, l'optimum relâché est (1,86 ; 0) : aucun arrondi n'approche le vrai optimum (0 ; 3), situé ailleurs. Arrondir reste acceptable pour de grandes quantités : 3 712 boîtes ou 3 713, peu importe. Mais pour de petits nombres coûteux, il faut un vrai calcul.

Planche 2

Décisions binaires : traduire le oui et le non

Une variable binaire ne vaut que 0 ou 1 : ouvrir ou fermer, sélectionner ou exclure. C'est un outil d'une puissance étonnante, car des règles de logique deviennent de simples inégalités. Cinq projets, A à E, soit 32 combinaisons possibles : activez les règles et regardez ce qu'il reste.

Chaque case est une combinaison de projets, écrite ABCDE (1 = retenu). Bleu : admissible. Gris : éliminé par une règle. Bord rouge : la meilleure. Bord noir : votre choix (cliquez sur une case).

Votre choix–

Sa valeur, son coût–

Combinaisons encore admissibles–

Meilleure combinaison–

Contrôle, séparation et évaluation : écart / nœuds–

Ce que l'on veut dire	Inégalité avec des variables 0-1	Lecture
Au plus 3 projets	a + b + c + d + e ≤ 3	On compte les 1
A et B s'excluent	a + b ≤ 1	Jamais les deux à 1
Si C, alors D	c ≤ d	c = 1 force d = 1
Au moins l'un de D et E	d + e ≥ 1	Pas les deux à 0
Produire seulement si l'usine est ouverte	q ≤ M · y	y = 0 force q = 0 (voir planche 5)

Ce qu'il faut retenir. Le mot « si » n'existe pas dans un programme linéaire, mais les binaires le remplacent. Le prix à payer se voit dans la grille : chaque variable binaire de plus double le nombre de combinaisons. Avec 30 projets, on dépasse le milliard ; avec 60, examiner un milliard de combinaisons par seconde prendrait plus de 30 ans. Il faut donc une méthode plus astucieuse que tout essayer.

Planche 3

Trois problèmes types : sac à dos, couverture, localisation

De très nombreux problèmes réels sont des variantes de ces trois modèles. Ils se reconnaissent à leur structure, et s'écrivent en quelques lignes.

Choisir sous une limite. Un randonneur choisit ce qu'il emporte : x_i = 1 s'il prend l'objet i. Il en va de même pour un budget d'investissements ou une capacité de chargement.

maximiser Σ v_i x_i sous Σ p_i x_i ≤ C, x_i ∈ {0 ; 1}

Chaque bloc est un objet, sa largeur est son poids, le nombre sa valeur. De haut en bas : votre sac, le meilleur sac, et la règle « meilleur rapport valeur/poids d'abord ». Trait rouge : la capacité.

Capacité du sac

Votre sac : valeur et poids–

Valeur optimale–

Meilleur rapport d'abord–

Borne de la relaxation (un objet coupé)–

Contrôle : table dynamique / nœuds de l'arbre sur 1 024 sacs–

Tout desservir au moindre coût. Où placer des casernes pour que chaque village soit à moins de R kilomètres de l'une d'elles ? x_s = 1 si on construit sur le site s. Chaque village donne une contrainte : au moins un site proche doit être retenu.

minimiser Σ x_s sous Σ_{s proche de v} x_s ≥ 1 pour chaque village v, x_s ∈ {0 ; 1}

Carrés : les sites possibles, à activer d'un clic. Ronds : les villages, rouges s'ils ne sont pas couverts. Bouton « Optimal » : la meilleure solution.

Rayon d'intervention R

–

Votre choix : casernes, villages couverts–

Minimum de casernes–

Règle gloutonne–

Borne de la relaxation–

Contrôle : énumération des 512 choix / nœuds de l'arbre–

Ouvrir, puis affecter. Où ouvrir des dépôts, sachant qu'ouvrir coûte, mais que la distance aussi ? y_s = 1 si on ouvre le site s ; x_sk = 1 si le client k est servi par s. On peut écrire de deux façons que seul un dépôt ouvert sert des clients :

forme forte : x_sk ≤ y_s pour chaque couple ; forme faible : Σ_k x_sk ≤ n · y_s pour chaque site

Carrés : les dépôts possibles, à ouvrir ou fermer d'un clic. Points : les clients, reliés au dépôt ouvert le plus proche.

Coût fixe d'ouverture d'un dépôt

Votre choix : coût fixe + transport–

Coût optimal, dépôts ouverts–

Forme forte : borne de la relaxation, nœuds–

Forme faible : borne de la relaxation, nœuds–

Contrôle : les 63 ouvertures possibles, écart–

La leçon cachée dans l'onglet Localisation. Les deux formes décrivent exactement les mêmes solutions entières, et la forme faible a bien moins de contraintes. Pourtant, sa relaxation est très mauvaise et il faut des dizaines de nœuds, alors que la forte conclut souvent dès le premier calcul. En nombres entiers, une bonne écriture vaut mieux qu'un calcul plus puissant.

Planche 4

Séparation et évaluation : tout essayer sans tout essayer

Séparer : si l'optimum relâché a x = 2,25, alors toute solution entière a soit x ≤ 2, soit x ≥ 3. On coupe le problème en deux, sans perdre aucune solution entière. Évaluer : la relaxation de chaque morceau borne tout ce qu'il contient. Si cette borne ne dépasse pas la meilleure solution déjà connue, on abandonne tout le morceau, sans l'explorer.

L'arbre. Bleu : séparé. Vert : solution entière trouvée. Orange : abandonné, sa borne ne peut plus battre le meilleur. Rouge : domaine vide. Gris : en attente. Cliquez sur un nœud pour voir son morceau.

En bleu, ce qui reste à explorer. Plus foncé et encadré : le morceau du nœud choisi, avec son optimum relâché (croix violette). Point rouge : la meilleure solution entière connue.

–

La borne supérieure (bleu) descend, la meilleure solution connue (rouge) monte. L'écart entre les deux mesure ce qu'il reste à prouver. Quand elles se touchent, c'est fini.

Nœuds créés–

Meilleure solution connue–

Borne supérieure–

Écart restant–

Plans entiers admissibles–

Contrôle, examen de tous les plans : écart–

Ce qu'il faut retenir. À tout instant, on tient deux nombres : la meilleure solution trouvée, et une borne que nul ne peut dépasser. On peut donc s'arrêter avant la fin, en sachant de combien on peut encore se tromper. C'est pourquoi un logiciel annonce : « solution à moins de 1 % de l'optimum ». L'ordre d'exploration change l'effort, parfois beaucoup, mais jamais le résultat.

Planche 5

Introduction aux coupes et à la programmation mixte

Deux idées qui font la force des logiciels actuels. Les coupes resserrent le domaine autour des points entiers. La programmation mixte associe des décisions entières et des quantités continues.

Une coupe est une inégalité supplémentaire qui retire l'optimum fractionnaire sans éliminer aucun point entier. Si l'on pouvait écrire la forme idéale, l'enveloppe convexe des points entiers (pointillés verts), chaque sommet serait entier, et le simplexe suffirait. Ralph Gomory a montré en 1958 comment lire une telle coupe dans le tableau du simplexe.

Bleu : le domaine courant. Rouge qui s'efface : ce que la coupe vient de retirer. Traits violets : les coupes. Pointillés verts : l'enveloppe convexe des points entiers. Croix violette : l'optimum relâché courant.

–

La borne de la relaxation après chaque coupe (bleu), qui descend vers l'optimum entier (trait rouge).

Optimum relâché courant–

Optimum entier (par énumération)–

Points entiers perdus par les coupes–

Nœuds d'arbre nécessaires à ce stade–

1 500 problèmes : terminés par les coupes seules–

Comment se fabrique une coupe. Prenons une ligne du tableau final où la valeur n'est pas entière. Tous les coefficients sont arrondis vers le bas, et comme les variables sont positives, l'inégalité reste vraie : x + ⌊a⌋ s ≤ b. Or le membre de gauche est entier pour tout point entier, donc on peut aussi arrondir b vers le bas. Le point fractionnaire est exclu, aucun point entier ne l'est. Une coupe ne réduit pas toujours l'arbre : sur le problème 2, il passe de 7 à 9 nœuds avant de tomber à 1. En pratique, on combine coupes et arbre : c'est le branch and cut.

Une usine ouverte se paie d'un coût fixe, puis à l'unité. Une variable binaire y dit si elle est ouverte, une variable continue q dit combien elle produit. L'inégalité q ≤ M · y les relie : si y = 0, la production est nulle. Faut-il produire dans trois usines pour satisfaire une demande D ?

minimiser Σ (f_i y_i + c_i q_i) sous Σ q_i ≥ D, q_i ≤ cap_i, q_i ≤ M y_i, y_i ∈ {0 ; 1}, q_i ≥ 0

Usine	Coût fixe	Coût à l'unité	Capacité
A, grande et moderne	500 €	2 €	80
B, moyenne	200 €	5 €	60
C, petite et souple	100 €	8 €	50

Coût selon la demande, pour chaque combinaison d'usines (traits fins). En rouge, le meilleur plan, à chaque demande : il présente des sauts. En pointillés : la borne de la relaxation pour le M choisi.

Le coût de l'usine A selon sa production. En rouge, le vrai coût, avec le saut du coût fixe. En violet, ce que voit la relaxation : y = q / M, soit un coût fixe réparti, d'autant plus faible que M est grand.

Demande D

Valeur du « grand M »

–

Productions A ; B ; C–

Coût optimal–

Borne de la relaxation–

Écart entre la borne et l'optimum–

Nœuds de l'arbre–

Contrôle, 8 combinaisons d'usines : écart–

Le « grand M » n'est pas anodin. Le choisir très grand est tentant, car c'est sans risque, et le résultat reste juste. Mais la relaxation voit alors un coût fixe presque nul, et sa borne ne vaut plus rien. Il faut prendre le plus petit M valable : ici, la capacité de l'usine. Remarquez aussi que le coût total n'est pas régulier : une demande un peu plus forte peut obliger à ouvrir une usine de plus, et faire bondir le coût.

Ce qu'il faut garder

Écrire

Les entiers comptent ; les binaires disent oui ou non et traduisent la logique. Une même réalité peut s'écrire de plusieurs façons : la meilleure écriture est celle dont la relaxation est la plus serrée.

Encadrer

La relaxation donne une borne, toute solution entière donne l'autre. La résolution consiste à resserrer cet encadrement, jusqu'à la preuve ou jusqu'à un écart acceptable.

Combiner

La séparation découpe, les coupes resserrent, les heuristiques trouvent vite de bonnes solutions. Les logiciels modernes font tout cela ensemble, mais ne peuvent rien contre une écriture mal posée.

Pour aller plus loin

Dans ce cahier. La programmation linéaire présente le simplexe, base de chaque évaluation. Le problème du sac à dos approfondit ce problème : programmation dynamique, instances difficiles. La localisation des installations stratégiques traite p-médiane, p-centre et couverture sur un territoire. Le voyageur de commerce montre ce qu'une bonne borne permet de prouver.

Sur les calculs. Sur les deux variables de la planche 4, la relaxation est résolue en découpant le polygone, puis la solution est comparée à l'examen de tous les points entiers. Les autres arbres utilisent le simplexe à deux phases, et séparent sur la variable la plus fractionnaire, en profondeur. Les coupes sont de Gomory, écrites à coefficients entiers. Chaque coupe a été testée sur 1 500 problèmes : aucun point entier n'a été éliminé.