<!-- Slide number: 1 -->
# Outils de Recherche opérationnelle en Génie MTH 8414
Programmation en nombre entier:
Méthode de résolution et astuces de modélisation
<!-- Slide number: 2 -->
Types de problème d’optimisation
Programme Linéaire en Nombre Entier (PLNE ou IP) :
Programme Linéaire en Nombre Entier Mix (MIP) :
Ces problèmes sont théoriquement très difficiles, mais en pratique ils peuvent (souvent) être résolus très rapidement.
<!-- Slide number: 3 -->
Formulation PLNE
X
on obtient un PL nommé
“Relaxation Linéaire”
Résolu par séparation et évaluation progressive
on branche sur les variables de décision
la relaxation linéaire nous donne des bornes inférieures.
3
<!-- Slide number: 4 -->
Méthodes de résolution pour PL
Algorithme du simplex
Une solution optimale se trouve nécessairement sur un point extrême.
Donc on peut la trouver en parcourant les arêtes du polyèdre.
x2
x1
cT
<!-- Slide number: 5 -->
Méthodes de résolution pour PL
Méthode par Points Intérieurs
Méthode dites “Barrières”
Formulation “Primal-Dual”
Pas de Newton
Avantages
Permet de résoudre de très gros problèmes
Preuve d’optimalité (comme le simplex)
x2
x1
-cT
<!-- Slide number: 6 -->
Méthodes de résolution pour PLNE
Énumération (Recherche Arborescente, Programmation Dynamique)
Garantie de trouver une solution réalisable entière.
Mais le temps de calcul croît exponentiellement avec la taille.
x1=0
x1=2
x1=1
X2=0
X2=1
X2=2
X2=0
X2=1
X2=2
X2=0
X2=1
X2=2
<!-- Slide number: 7 -->
Méthodes de résolution pour PLNE
Résoudre un PL puis arrondir ?
Solution entière
-cT
x2
x1
Solution du PL
<!-- Slide number: 8 -->
Méthodes de résolution pour PLNE
Le PL fournit une borne inf (ou sup si on maximise) sur la valeur du PLNE.
Mais en arrondissant, on peut être très loin d’une solution entière…
x2
x1
-cT
<!-- Slide number: 9 -->
Approche combinée pour PLNE.
On peut combiner les deux approches
Résoudre le PL pour obtenir une solution.
Créer deux sous-problèmes en ajoutant des contraintes.
x2
x1
x2
x1
x1≥2
-cT
-cT
x1≤1
<!-- Slide number: 10 -->
Séparation et évaluation progressive
Principe
Chercher systématiquement toutes les combinaisons variables-valeurs possibles.
Utiliser une heuristique pour déterminer sur quelle variable brancher.
Utiliser les bornes inférieures pour limiter la recherche.
Publicité
Construire un arbre de recherche.
10
<!-- Slide number: 11 -->
SEP: le branchement
Imaginez un problème avec 3 variables
a, b, c є {0, 1}
Branchement
a = 0
a = 1
b = 0
b = 1
b = 0
b = 1
c = 0
c = 1
c = 0
c = 1
c = 0
c = 1
c = 0
c = 1
100
90
110
115
80
90
100
110
11
<!-- Slide number: 12 -->
SEP: utilisation des bornes inférieures
Si nous pouvions calculer une borne sur le coût minimal d’un noeud.
a = 0
a = 1
50
b = 0
b = 1
b = 0
70
80
c = 0
c = 1
c = 0
85
95
80
100
90
80
12
<!-- Slide number: 13 -->
Séparation et évaluation progressive
Mieux connu sous le nom anglais “branch and bound”
Branch: assigne heuristiquement une valeur à une variable
Crée deux sous problèmes
Bound: comparer la borne inférieure à la meilleure solution connue
Ça ne vaut pas la peine d’explorer le sous-arbre si
Minimisation: si BorneInf >= MeilleureSolution,
Maximisation: si BorneSup <= MeilleureSolution,
13
<!-- Slide number: 14 -->
SÉP pour résoudre des PLNE
Généralement la borne inférieure = la relaxation linéaire.
On l’obtient en « relaxant » les contraintes d’intégrité.
On choisit une variable non entière et on la force soit à :
être plus grande ou égale à l’entier supérieur ou
être plus petite ou égale à l’entier inférieur.
14
<!-- Slide number: 15 -->
Branch and Bound: un exemple
Relaxation linéaire (ou continue)
15
<!-- Slide number: 16 -->
Branch and Bound: un exemple
Premier noeud
(solution optimale de la relaxation linéaire)
Valeur optimale
P0 : z0 = 282,5
x1 = 4,5
x2 = 4,75
Variables non nulles
16
<!-- Slide number: 17 -->
Branch and Bound
P0
noeud-père
P1 : z1 = 265
x1 = 4
x2 = 4,5
Publicité
P2 : z2 = 275
x1 = 5
x2 = 4,5
noeuds-fils
x1 £ 4
x1 ³ 5
17
<!-- Slide number: 18 -->
Branch and Bound: un exemple
P0
x1 £ 4
x1 ³ 5
P1 : z1 = 265
x1 = 4
x2 = 4,5
P2
x2 £ 4
x2 ³ 5
P3 : z3 = 260
x1 = 6
x2 = 4
P4
Aucune solution
admissible
18
Notes:
<!-- Slide number: 19 -->
Branch and Bound
Au final…
P0
x1 ³ 5
x1 £ 4
P1
P2
x2 ³ 5
x2 ³ 5
x2 £ 4
x2 £ 4
P5 : z5 = 240
x1 = 4
x2 = 4
P6
Aucune solution
admissible
P3 : z3 = 260
x1 = 6
x2 = 4
P4
Aucune solution
admissible
19
<!-- Slide number: 20 -->
Calculs incrémentaux
En règle générale, pour calculer une solution optimale d’un nœud-fils, il sera plus rapide de modifier le tableau optimal du nœud père plutôt que de reprendre les calculs de l’algorithme du simplexe à partir de leur début.
Reprendre le tableau P0
P0
Reprendre le tableau P2
P1
P2
P3
P4
P5
P6
20
<!-- Slide number: 21 -->
Algorithme (problème de minimisation)
Les notations suivantes sont utilisées :
L : ensemble des sous-problèmes actifs;
zU : la borne supérieure sur la valeur optimale de MIP ;
ziLP : la valeur optimale du problème linéaire i ;
zjLP : la borne inférieure sur la valeur optimale du sous-problème j ;
X* : La meilleure solution réalisable.
21
<!-- Slide number: 22 -->
L'algorithme comprend 6 étapes :
Étape 1 : Initialisation
L = {relaxation initiale}, zU = .
Étape 2 : Test d'optimalité
Si L = , x* est la solution optimale.
Étape 3
Choisir un sous-problème i et l'éliminer de la liste L.
Étape 4
Résoudre la relaxation linéaire de i. Si elle n'est pas réalisable, allez à l'étape 3 Sinon, poser ziLP et xi la valeur et la solution optimales obtenues.
Étape 5
Si ziLP zU , aller à l'étape 2. Si xi n'est pas entière, aller à l'étape 6.
Sinon zU = ziLP, x* = xi.
Éliminer de L tous les sous-problèmes j tels que zjLP zU et aller à l'étape 2.
Étape 6
Choisir une variable binaire ayant une valeur fractionnaire dans la solution xi et subdiviser le problème i à partir de cette variable. Ajouter les nouveaux problèmes à L.
22
<!-- Slide number: 23 -->
Algorithme (remarque)
Pour que l'algorithme soit complètement défini, on doit fixer:
à l'étape 3, la sélection du sous-problème à résoudre et
Publicité
à l'étape 6, la règle de séparation du nœud courant.
Ces deux règles (choix de nœuds et choix de variables) sont cruciales quant à l'efficacité de l'approche de séparation et d'évaluation progressive.
x2
x1
Branche x1
-cT
Branche x2
Branche x1 puis x2
23
<!-- Slide number: 24 -->
Un autre exemple
Soit le problème de PLNE suivant:
Et la notation
24
<!-- Slide number: 25 -->
11-25
<!-- Slide number: 26 -->
Ajout de plans coupant (branch and cut)
L’idée est d’ajouter des coupes au PL pour améliorer la qualité de la borne.
x2
x1
Toutes les solutions entières sont préservées
La solution actuelle du PL devient non réalisable.
Coupe ajoutée (bleu)
<!-- Slide number: 27 -->
Trucs et astuces de modélisation
Comment modéliser les cas où l’on est en présence de:
variables ont des domaines discontinus;
certaines ressources qui ont des coûts fixes;
disjonctions de contraintes;
contraintes conditionnelles
de SOS et des fonctions linéaires par morceaux
des produits de variables
27
<!-- Slide number: 28 -->
Variables avec domaines discontinues
Que faire avec le cas où soit x = 0 OU l <= x <= u
On peut considérer ceci comme deux contraintes, mais elles ne peuvent être vraies toutes les deux à la fois…
Pouvez-vous trouver des exemples d’applications ?
Comment modéliser ceci avec un PLNE ?
28
<!-- Slide number: 29 -->
Variables avec domaines discontinues
On utilisera une variable indicatrice:
Qu’on liera avec la variable originale par les contraintes suivantes:
Y = 0 implique donc x = 0 et y = 1 implique que l <= x <= u
29
<!-- Slide number: 30 -->
Les coûts fixes
Soit le problème suivant:
La fonction de coût n’est ni linéaire ni continue...
À quelle application pensez-vous ?
Comment résoudre ce problème ?
30
<!-- Slide number: 31 -->
Les coûts fixes
Si on connaît une borne u suffisamment grande pour x et qu’on introduit une variable indicatrice y
On relier x et y par x <= yu
L’objectif devient donc:
Et le problème devient:
31
<!-- Slide number: 32 -->
Une disjonction de contrainte
Soit le problème suivant:
Où soit (1) ou (2) doit être respectée
Des applications ?
Comment faire ?
32
<!-- Slide number: 33 -->
Une disjonction de contraintes
Encore une fois on introduira une variable supplémentaire y ainsi que deux grands nombres (M1 et M2).
En modifiant (1) et (2) de la manière suivante:
On s’assure qu’une des deux contraintes devra être satisfaite.
33
<!-- Slide number: 34 -->
Contraintes conditionnelles
Une variante de ce problème survient lorsque certaines contraintes sont conditionnelles:
Donnez des exemples d’application ?
Comment traiter ce cas ?
34
<!-- Slide number: 35 -->
Publicité
Contraintes conditionnelles
Pour adresser ce cas, nous devons nous tourner vers la logique
L’équation logique qui nous intéresse est (A implique B)
Cette équation est équivalente à (non-A OU B)
On a donc une disjonction de contraintes, qu’on peut traiter comme précédemment…
Devient:
Sauf qu’ici on a un signe > qu’on ne peut traiter en PL…
35
<!-- Slide number: 36 -->
Contraintes conditionnelles
On introduira une petite valeur epsilon
Pour obtenir:
Qui peut être réécrit comme:
36
<!-- Slide number: 37 -->
Les SOS (Special Ordered Sets)
Considérer le cas particulier suivant:
Votre modèle comporte une série de décision oui/non ordonnée.
Seulement une décision « oui » est possible
Entre deux décisions « oui » on préfèrera toujours celle qui est la première dans la série.
Pour ce cela, on dispose généralement d’une série de variables booléennes yi telles que
On peut généraliser ce cas à :
Aux variables générales xi tel que 0 <= xi <= u et sujet à
On peut aussi considérer le cas où deux décisions « oui » sont permises, mais elles doivent être consécutives.
Les solveurs ont des objets de modélisation SOS1 et SOS2 qui implémentent ces conditions de manières plus efficaces lors du branch and bound.
37
<!-- Slide number: 38 -->
Fonctions linéaires par morceaux
Soit le problème suivant:
Ici on remarque que l’objective, bien que non linéaire, est séparable.
C’est-à-dire que l’objectif est une somme de fonctions définies sur une variable à la fois.
Séparable Non séparable
38
<!-- Slide number: 39 -->
Fonctions linéaires par morceaux
Soit la fonction
Soit x1, x2, x3, x4 des points de « cassure » (breakpoints) auquel on évalue la fonction f(x) (soit 0,1,2,4)
On approxime donc linéairement tout point situé entre deux cassures, par exemple f(3) = ½f(2) + ½f(4) = ½1 + ½8 = 5.
39
<!-- Slide number: 40 -->
Fonctions linéaires par morceaux
Une des manières de traiter ces fonctions est d’utiliser la λ-formulation.
Soit λ1, λ2, λ3, λ4, 4 poids non négatifs dont la somme = 1, alors la fonction linéaire par morceaux précédente peut-être exprimée par:
Comme au plus deux λ peuvent être non négatifs, et que ceux-ci doivent en plus être consécutifs, on peut ajouter une contrainte SOS2(λ).
La majorité des solveurs ont un objet « Piecewise Linear » que vous pouvez utiliser directement.
40
<!-- Slide number: 41 -->
Éliminer les produits de variables
Que faire des problèmes où des termes contiennent le produit de deux variables booléennes x1x2
On peut faire disparaître ce produit en introduisant une nouvelle variable booléenne y qui doit être égale au produit x1x2.
Pour ce faire il faut ajouter les contraintes suivantes:
41
<!-- Slide number: 42 -->
Éliminer les produits de variables
Que faire maintenant si doit traiter un produit x1x2 où x1 est une variable binaire et x2 est une variable continue tel que 0 <= x2 <= u ?
On introduit une variable continue y définie comme y = x1x2 en ajoutant les contraintes ci-dessous imposant le comportement:
42
<!-- Slide number: 43 -->
Excercise de modélisation
On veut assembler l’horaire hebdomadaire de travail d’une unité d’infirmières sachant que:
On a trois quarts de 8h de travail à couvrir (J,S,N)
Le nombre d’infirmières requises de dq où q est un quart de travail (J,S,N)
Une infirmière doit avoir 16h de repos entre deux quarts.
Les contraintes suivantes doivent être respectées
Si on emploie une infirmière pendant la semaine, elle doit travailler au moins 3 quarts.
Une infirmière doit avoir congé soit
a) toutes les nuits de la semaine
b) toute la fin de semaine.
Si une infirmière travaille 4 quarts de travaille, elle doit avoir congé la fin de semaine.
Chaque infirmière donne une liste de jours de congé souhaitée (et ordonnées), on doit lui donner au moins un de ces choix.
Il faut minimiser les coûts sachant que:
Si on emploie une infirmière il faut payer l’agence un montant fixe de F$ + G$ par quart travaillé.
En plus, il est permis de ne pas avoir le bon nombre d’infirmières, mais il faut payer une pénalité de P(k) $ ou k est la différence entre le nombre souhaité le nombre d’infirmières assignées
43