Outils de Recherche
Opérationnelle en Génie - MTH 8414
Programmation en nombres entiers
• Introduction
• Résolution
Louis-Martin Rousseau
Office: A520.21 Tel.: #4569
[Link]@[Link]
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.
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.
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
cT
x1
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 x2
• Permet de résoudre de très gros problèmes
• Preuve d’optimalité (comme le simplex)
-cT
• Preuve de convergence en un temps polynomial
x1
Comment résoudre un PLNE ?
Résoudre un PL puis arrondir ?
Solution entière
x2
Solution du PL
x1 -cT
Comment résoudre un 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
-cT
x1
Comment résoudre un PLNE ?
Peut-on énumérer les solutions ?
• Énumération (Recherche Arborescente, Programmation Dynamique)
x1=0 x1=1 x1=2
x2=0 x2=1 x2=2 x2=0 x2=1 x2=2 x2=0 x2=1 x2=2
• Garantie de trouver une solution réalisable entière.
• Mais le temps de calcul croît exponentiellement avec la taille.
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 x2
x1≥2
-cT -cT
x1 x1≤1 x1
10
SÉP: 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
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
Outils de Recherche
Opérationnelle en Génie - MTH 8414
Programmation en nombres entiers
• Introduction
• Résolution
Louis-Martin Rousseau
Office: A520.21 Tel.: #4569
[Link]@[Link]
13
Séparation et évaluation progressive
Mieux connu sous le nom anglais “branch and bound”
• Séparation (branch): assigne heuristiquement une valeur à une variable
• Crée deux sous problèmes
• Évaluation (borne): 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,
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.
15
Branch and Bound:
un exemple
max 𝑧 = 10𝑥! + 50𝑥"
s.c.
−𝑥! + 2𝑥" ≤ 5
𝑥! + 2𝑥" ≤ 14 Relaxation linéaire (ou continue)
𝑥! ≤8
𝑥! , x2 ≥0
𝑥! , 𝑥" . entiers
16
Branch and Bound
un exemple
Premier noeud
(solution optimale de la relaxation linéaire)
P0 : z0 = 282,5 Valeur optimale
x1 = 4,5 Variables non nulles
x2 = 4,75
17
Branch and Bound
un exemple
P0 noeud-père
x1 ≤ 4 x1 ≥ 5
P1 : z1 = 265 P2 : z2 = 275
x1 = 4 x1 = 5
x2 = 4,5 x2 = 4,5
noeuds-fils
18
Branch and Bound
un exemple
P0
x1 ≤ 4 x1 ≥ 5
P1 : z1 = 265 P2
x1 = 4
x2 ≤ 4 x2 ≥ 5
x2 = 4,5
P3 : z3 = 260 P4
x1 = 6 Aucune solution
x2 = 4 admissible
19
Branch and Bound
Finalement
P0
x1 ≤ 4 x1 ≥ 5
P1 P2
x2 ≤ 4 x2 ≥ 5 x2 ≤ 4 x2 ≥ 5
P5 : z5 = 240 P6 P3 : z3 = 260 P4
x1 = 4 Aucune solution x1 = 6 Aucune solution
x2 = 4 admissible x2 = 4 admissible
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 à partir de la solution P0
P0
Reprendre à
partir de la
P1 P2
solution P2
P3 P4 P5 P6
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.
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.
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
• à 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
Branche x2
-cT
x1
Branche x1 Branche x1
24
Un autre exemple
Soit le problème de PLNE suivant: (𝑃): min 𝑧 = −3𝑥" − 3𝑥# − 13𝑥$
sujet à :
−3𝑥" + 6𝑥# + 7𝑥$ ≤ 8
6𝑥" − 3𝑥# + 7𝑥$ ≤ 8
𝑥" ≤ 5
𝑥# ≤ 5
𝑥$ ≤ 5
𝑥" , 𝑥# , 𝑥$ ≥ 0 et entières.
Et la notation 𝑋 = 𝑥 ∈ 𝐼 $ : −3𝑥" + 6𝑥# + 7𝑥$ ≤ 8, 6𝑥" − 3𝑥# + 7𝑥$ ≤ 8
𝑧 = 𝑐 % 𝑥 = −3𝑥" − 3𝑥# − 13𝑥$
Ajout de plans coupants (branch and cut)
L’idée est d’ajouter des coupes au PL pour améliorer la qualité de la borne.
x2
l Toutes les solutions
entières sont préservées
l La solution actuelle du PL
devient non réalisable.
x1
Coupe ajoutée
