Outils de Recherche opérationnelle en Génie MTH 8414

Ce matériel couvre les méthodes de programmation en nombre entier, notamment la résolution des programmes linéaires en nombres entiers (PLNE) et mixtes (MIP), ainsi que des astuces de modélisation avancées. Il s’adresse aux étudiants et professionnels en génie et recherche opérationnelle souhaitant maîtriser les techniques d’optimisation combinatoire et la modélisation de contraintes complexes.

Types de problèmes d’optimisation

On distingue principalement deux types de problèmes :

• Programme Linéaire en Nombre Entier (PLNE ou IP) : toutes les variables de décision sont entières.
• Programme Linéaire en Nombre Entier Mixte (MIP) : certaines variables sont entières, d’autres continues.

Ces problèmes sont théoriquement difficiles (NP-difficiles), mais en pratique, ils peuvent souvent être résolus rapidement grâce à des méthodes efficaces.

Formulation du PLNE

Un PLNE est formulé comme un programme linéaire classique, mais avec la contrainte que certaines variables doivent prendre des valeurs entières. En relaxant cette contrainte d’intégrité, on obtient la relaxation linéaire, qui est un programme linéaire classique. Cette relaxation fournit une borne inférieure (en cas de minimisation) pour la valeur optimale du PLNE.

Méthodes de résolution pour les programmes linéaires (PL)

Les méthodes classiques pour résoudre un PL sont :

• Algorithme du simplex : il exploite le fait qu’une solution optimale se trouve nécessairement sur un sommet du polyèdre des contraintes. Il parcourt donc les arêtes du polyèdre pour trouver la solution optimale.
• Méthodes par points intérieurs (ou méthodes barrières) : elles utilisent des techniques de type primal-dual et Newton pour résoudre efficacement de très grands problèmes. Elles garantissent aussi l’optimalité.

Méthodes de résolution pour les PLNE

Les PLNE sont plus complexes à résoudre. Plusieurs approches existent :

• Énumération (recherche arborescente, programmation dynamique) : garantit une solution entière réalisable, mais le temps de calcul croît exponentiellement avec la taille du problème.
• Résoudre la relaxation linéaire puis arrondir : simple mais souvent inefficace, car l’arrondi peut s’éloigner beaucoup de la solution entière optimale.
• Approche combinée : résoudre la relaxation linéaire, puis créer deux sous-problèmes en ajoutant des contraintes sur une variable fractionnaire (par exemple x1 ≤ 1 et x1 ≥ 2), ce qui mène à la méthode dite de séparation et évaluation progressive.

Séparation et évaluation progressive (Branch and Bound)

Cette méthode consiste à :

• Construire un arbre de recherche en branchant successivement sur des variables non entières.
• Utiliser la relaxation linéaire pour calculer des bornes inférieures sur le coût minimal dans chaque sous-arbre.
• Élaguer les branches dont la borne inférieure est pire que la meilleure solution entière connue.

Par exemple, pour un problème avec trois variables binaires a, b, c, on crée un arbre où chaque noeud correspond à une affectation partielle des variables. On calcule la valeur optimale de la relaxation linéaire à chaque noeud, puis on décide de poursuivre ou non l’exploration.

Exemple simplifié de Branch and Bound

Considérons un problème avec deux variables x1 et x2 :

• Relaxation linéaire initiale (P0) : solution optimale z0 = 282,5 avec x1 = 4,5 et x2 = 4,75 (non entiers).
• On branche sur x1 :
• P1 : x1 ≤ 4, solution z1 = 265 avec x1 = 4, x2 = 4,5
• P2 : x1 ≥ 5, solution z2 = 275 avec x1 = 5, x2 = 4,5
• On branche ensuite sur x2 dans P2 :
• P3 : x2 ≤ 4, solution z3 = 260 avec x1 = 6, x2 = 4
• P4 : x2 ≥ 5, aucune solution admissible
• On continue ainsi, éliminant les noeuds sans solution admissible ou dont la borne inférieure est pire que la meilleure solution entière connue.

Calculs incrémentaux

Pour accélérer le calcul des solutions optimales des noeuds fils, on modifie généralement le tableau optimal du noeud père plutôt que de recalculer depuis zéro avec l’algorithme du simplex.

Algorithme Branch and Bound pour un problème de minimisation

Les notations utilisées :

• L : ensemble des sous-problèmes actifs
• zU : borne supérieure sur la valeur optimale du MIP
• ziLP : valeur optimale de la relaxation linéaire du sous-problème i
• zjLP : borne inférieure sur la valeur optimale du sous-problème j
• X* : meilleure solution réalisable entière connue

L’algorithme comprend six étapes :

1. Initialisation : L = {relaxation initiale}, zU = +∞
2. Test d’optimalité : si L est vide, X* est la solution optimale.
3. Sélection : choisir un sous-problème i dans L et le retirer.
4. Résolution : résoudre la relaxation linéaire de i. Si non réalisable, retourner à l’étape 3. Sinon, poser ziLP et xi la solution obtenue.
5. Comparaison : si ziLP ≥ zU, retourner à l’étape 2. Sinon, si xi est entière, mettre à jour zU = ziLP et X* = xi, éliminer de L tous les sous-problèmes j avec zjLP ≥ zU, puis retourner à l’étape 2. Sinon, passer à l’étape 6.
6. Séparation : choisir une variable binaire fractionnaire dans xi, subdiviser i en deux sous-problèmes selon cette variable, ajouter ces sous-problèmes à L, puis retourner à l’étape 2.

Remarques sur l’algorithme

Les choix de la sélection du sous-problème à résoudre (étape 3) et de la variable sur laquelle brancher (étape 6) sont cruciaux pour l’efficacité de la méthode.

Ajout de plans coupants (Branch and Cut)

Pour améliorer la qualité des bornes, on peut ajouter des plans coupants au programme linéaire. Ces coupes éliminent certaines solutions non entières sans exclure aucune solution entière admissible, ce qui resserre la relaxation linéaire.

Astuces de modélisation

Variables avec domaines discontinus

Pour modéliser une variable x qui doit être soit nulle, soit dans un intervalle [l, u], on introduit une variable indicatrice binaire y liée à x par :

• Si y = 0 alors x = 0
• Si y = 1 alors l ≤ x ≤ u

Les contraintes associées sont :

l * y ≤ x ≤ u * y

Coûts fixes

Lorsque la fonction de coût comporte un terme fixe lié à l’utilisation d’une ressource, on peut modéliser cela en introduisant une variable indicatrice y et une borne supérieure u sur x, avec la contrainte :

x ≤ y * u

Le coût total devient alors une fonction linéaire en x et y, ce qui permet de conserver la linéarité du modèle.

Disjonction de contraintes

Pour modéliser un problème où au moins une contrainte parmi deux doit être satisfaite (par exemple (1) ou (2)), on introduit une variable binaire y et deux grands nombres M1 et M2, puis on modifie les contraintes :

(1) modifiée : contrainte ≤ M1 * y
(2) modifiée : contrainte ≤ M2 * (1 - y)

Ce mécanisme force la satisfaction d’au moins une des contraintes originales.

Contraintes conditionnelles

Pour traiter des contraintes conditionnelles du type « A implique B », on utilise la logique :

A ⇒ B est équivalent à ¬A ∨ B

Ce qui se traduit par une disjonction de contraintes. Pour gérer les inégalités strictes, on introduit une petite valeur ε > 0 afin de transformer l’implication en une contrainte linéaire adaptée.

Les SOS (Special Ordered Sets)

Les SOS sont des ensembles ordonnés de variables où :

• SOS1 : au plus une variable peut être non nulle.
• SOS2 : au plus deux variables consécutives peuvent être non nulles.

Ces structures sont utilisées pour modéliser des décisions ordonnées ou des fonctions linéaires par morceaux, et sont gérées efficacement par les solveurs lors du branch and bound.

Fonctions linéaires par morceaux

Une fonction non linéaire mais séparable peut être approchée par morceaux linéaires entre des points de cassure (breakpoints). Par exemple, pour une fonction f(x) évaluée en x1, x2, x3, x4, on peut approximer f(3) par :

f(3) = ½ * f(2) + ½ * f(4)

La λ-formulation utilise des poids λi ≥ 0 tels que la somme des λi = 1, et seulement deux λ consécutifs peuvent être non nuls (contrainte SOS2). La fonction est alors exprimée comme une combinaison convexe des valeurs aux points de cassure.

Éliminer les produits de variables

Pour traiter un produit de deux variables booléennes x1 x2, on introduit une variable booléenne y = x1 x2 avec les contraintes :

y ≤ x1
y ≤ x2
y ≥ x1 + x2 - 1

Si x1 est binaire et x2 continue avec 0 ≤ x2 ≤ u, on introduit une variable continue y = x1 x2 et on impose :

y ≤ u * x1
y ≤ x2
y ≥ x2 - u * (1 - x1)
y ≥ 0

Exercice de modélisation : horaire hebdomadaire d’infirmières

On souhaite planifier l’horaire hebdomadaire d’une unité d’infirmières avec les contraintes suivantes :

• Trois quarts de travail de 8h à couvrir : jour (J), soir (S), nuit (N).
• Nombre d’infirmières requises par quart.
• Une infirmière doit avoir 16h de repos entre deux quarts.
• Si une infirmière est employée, elle doit travailler au moins 3 quarts.
• Une infirmière doit avoir congé soit toutes les nuits de la semaine, soit toute la fin de semaine.
• Si une infirmière travaille 4 quarts, elle doit avoir congé la fin de semaine.
• Chaque infirmière fournit une liste ordonnée de jours de congé souhaités, dont au moins un doit être accordé.

L’objectif est de minimiser les coûts sachant que :

• Si une infirmière est employée, un coût fixe F$ est payé à l’agence, plus un coût variable G$ par quart travaillé.
• Il est permis de ne pas respecter exactement le nombre d’infirmières requis, mais une pénalité P(k)$ est appliquée en fonction de la différence k entre le nombre souhaité et le nombre assigné.

Glossaire des termes clés

• PLNE (Programme Linéaire en Nombre Entier) : programme linéaire avec des variables entières.
• MIP (Mixed Integer Programming) : programme linéaire avec variables entières et continues.
• Relaxation linéaire : version du PLNE où la contrainte d’intégrité est levée.
• Simplex : algorithme pour résoudre les programmes linéaires en parcourant les sommets du polyèdre.
• Points intérieurs : méthode alternative au simplex utilisant des points à l’intérieur du polyèdre.
• Branch and Bound : méthode combinée de séparation et évaluation progressive pour résoudre les PLNE.
• Plan coupant (cutting plane) : contrainte ajoutée pour améliorer la relaxation linéaire sans exclure de solutions entières.
• Variable indicatrice : variable binaire utilisée pour modéliser des conditions logiques ou discontinuités.
• Disjonction de contraintes : situation où au moins une contrainte parmi plusieurs doit être satisfaite.
• Contraintes conditionnelles : contraintes qui s’appliquent seulement si une condition est vraie.
• SOS1 et SOS2 : ensembles ordonnés spéciaux de variables avec restrictions sur le nombre de variables non nulles.
• Fonction linéaire par morceaux : fonction définie par segments linéaires entre points de cassure.
• Produit de variables : terme non linéaire pouvant être linéarisé par introduction de variables auxiliaires et contraintes.

Points clés à retenir

• Les PLNE sont difficiles à résoudre mais la relaxation linéaire fournit des bornes utiles.
• La méthode Branch and Bound combine relaxation, branchement sur variables fractionnaires, et élagage grâce aux bornes.
• Les choix de variables pour le branchement et de sous-problèmes à explorer influencent fortement la performance.
• Les plans coupants améliorent la relaxation en excluant des solutions non entières.
• Les variables indicatrices permettent de modéliser des domaines discontinus, coûts fixes, disjonctions et contraintes conditionnelles.
• Les SOS et fonctions linéaires par morceaux facilitent la modélisation de décisions ordonnées et fonctions non linéaires.
• Les produits de variables peuvent être linéarisés pour conserver la structure du PLNE.
• La modélisation avancée permet de traiter des problèmes complexes comme la planification d’horaires avec contraintes multiples.