Optimiser dans l’incertain
Programmation robuste
Option 3A Optimisation 1
Alain Faye
1
Plan
• Programmation robuste
– Scenarios
• Différents critères de robustesse
• Moyenne ordonnée OWA
– Ensemble d’incertitude
• Contraintes avec coefficients incertains
• Programmation avec recours
– Recours robuste
– Recours avec OWA
• Modèles en AMPL
2
Programmation robuste
3
Données incertaines – Programmation robuste
On a un problème d’optimisation avec des données incertaines
Que faire ?
On pourrait optimiser la valeur moyenne de l’objectif par exemple
- Mais on n’a pas forcément connaissance des lois de probabilité suivies par les données
- De plus une solution qui optimise une valeur moyenne peut être mauvaise
pour certaines réalisations des données
L’approche robuste consiste à chercher une solution « bonne » quelque soit
la réalisation des données
4
Optimiser sous des données incertaines
Problème d’optimisation avec données incertaines
Ensemble fini de scenarios
Données incertaines modélisées par
Ensemble polyédrique
l’objectif
Incertitude sur
les contraintes
5
Approche par scenarios
6
Incertitude sur l’objectif
Problème d’optimisation min 𝑓(𝑥)
𝑥∈𝑋
Objectif incertain : S ensemble de scenarios possibles
Plusieurs objectifs 𝑓𝑠 𝑠 ∈ 𝑆 dépendant des scenarios
On a pu élaborer S un ensemble de scenarios envisageables
mais on n’a pas de loi de probabilité sur ces scenarios
7
Exemple
Plus court chemin de 1 à 4
2 (3 , 0)
(0 , 1)
3 2 scenarios sur la valeur des arcs
(0 , 3)
1 (2 , 0)
(3 , 2) 4
chemins valeur pour sc.1 valeur pour sc.2
1-2-3-4 5 1
1-2-4 0 4
1-4 3 2
Quel chemin choisir ?
8
Critères robustes
On minimise le pire coût
min max 𝑓𝑠 (𝑥)
𝑥∈𝑋 𝑠∈𝑆
chemins valeur sc.1 valeur sc.2 Max(sc1,sc2)
1-2-3-4 5 1 5
1-2-4 0 4 4
1-4 3 2 3
Min max = 3
On choisit chemin 1-4
Quoiqu’il arrive le coût ne dépassera pas 3
9
Critères robustes
On minimise le pire écartement par rapport au cout optimal
du scenario
∗
𝑥𝑠 = solution optimale pour le scenario s
∗
min max 𝑓𝑠 𝑥 − 𝑓𝑠 (𝑥𝑠 )
𝑥∈𝑋 𝑠∈𝑆
chemins val. sc.1 val. sc.2 val. sc1 - val. sc2 - max
min sc1 min sc2
1-2-3-4 5 1 5 0 5
1-2-4 0 4 0 3 3
1-4 3 2 3 1 3
min 0 1 3
On peut choisir chemin 1-4 ou 1-2-4
Quoiqu’il arrive l’écartement par rapport au cout optimal ne dépassera pas 3
10
Critères robustes
Le critère avec écartement nécessite la connaissance de la valeur optimale
pour chaque scenario => coûteux en temps de calcul
Dans la pratique, on utilise généralement le critère avec le coût absolu
11
Exercices
• Donner un programme mathématique (linéaire) pour calculer le plus court chemin
d’un sommet à un autre dans un graphe orienté.
• Pour un graphe avec un ensemble S de scenarios possibles sur les valeurs des arcs,
donner le programme mathématique qui calcule le chemin qui minimise
le pire des scenarios .
12
Minimiser l’espérance ?
• Ensemble de K scenarios S={s1,…,sK}. Si on
connaît la probabilité pk de chaque scenario k.
• On peut minimiser l’espérance de la fonction
σ𝐾
objectif: min 𝑘=1 𝑝𝑘 𝑓𝑠𝑘 (𝑥)
𝑥∈𝑋
– Si fs(x) est polynomiale, cela revient à minimiser
une fonction moyenne
• Et si on avait une idée sur la probabilité du
pire scenario, du deuxième pire scenario, etc…
13
Et si on minimisait la moyenne des
pires cas
• Le pire cas arrivera avec une probabilité 1 , le
deuxième pire cas avec probabilité 2 , le troisième
pire cas etc…
• On reste prudent : la probabilité du pire cas est la
plus haute, la probabilité du deuxième pire cas vient
en 2è position etc…
• ii=1 et i i+1 i
• Au lieu de minimiser le pire cas, on va minimiser la
moyenne ordonnée des cas
14
Moyenne ordonnée
𝑝
p critères 𝑐1 , 𝑐2 , ⋯ , 𝑐𝑝 , p poids décroissants 1 ≥ 2 ≥ ⋯ ≥ 𝑝 ≥ 0 avec σ𝑖=1 𝑖 = 1
On trie les critères dans l’ordre décroissant
𝑐(1) ≥ 𝑐(2) ≥ ⋯ ≥ 𝑐(𝑝)
(𝑖) désigne le critère en position 𝑖
Moyenne ordonnée OWA (Ordered Weighted Average)
1 𝑐(1) + 2 𝑐(2) + ⋯ + 𝑝 𝑐(𝑝)
15
Moyenne ordonnée
Exemple :
3 critères 𝑐1 = 4, 𝑐2 = 3, 𝑐3 = 5
Critères triés 𝑐(1) = 5, 𝑐(2) = 4, 𝑐(3) = 3
• Prenons 1 = 0,6 , 2 = 0,3 , 3 = 0,1
OWA = 0,6 × 5 + 0,3 × 4 + 0,1 × 3 = 4,5
• Prenons 1 = 1 , 2 = 0, 3 = 0
OWA = 5
16
OWA et problème d’optimisation
𝑆 ensemble de p scenarios , objectif dépendant des scenarios 𝑓𝑠 𝑠 ∈ 𝑆
𝑥 fixé 𝑓 1 (𝑥) ≥ 𝑓 2 (𝑥) ≥ ⋯ ≥ 𝑓 𝑝 (𝑥) le classement dépend de 𝑥
On minimise la moyenne ordonnée
min 𝑂𝑊𝐴 𝑥 = 1 𝑓 1 𝑥 +2 𝑓 2 𝑥 + ⋯ + 𝑝 𝑓 𝑝 (𝑥)
𝑥∈𝑋
Note : pour 1 = 1 , 2 = 0, ⋯ , 𝑝 = 0 on retrouve l’optimisation robuste
puisque l’on minimise le pire coût
17
Exemple OWA
Plus court chemin de 1 à 4
2 (0 , 2)
(1 , 0)
3 2 scenarios sur la valeur des arcs
(5 , 0)
1 (0 , 3)
(4 , 3) 4
chemins valeur pour sc.1 valeur pour sc.2
1-2-3-4 1 5
1-2-4 6 0
1-4 4 3
18
Exemple OWA
chemins valeur valeur OWA OWA
pour sc.1 pour sc.2 1=0,6 1=1 2=0
2=0,4
1-2-3-4 1 5 3,4 5
1-2-4 6 0 3,6 6
1-4 4 3 3,6 4
min 3,4 4
Avec une vision robuste, on choisit le chemin 1-4. On ne paiera pas plus que 4.
Si on estime que le second pire scenario a une chance (0,4) de se produire,
on choisit le chemin 1-2-3-4. On peut certes payer 5 si on n’a pas de chance
mais sinon on peut payer 1.
19
Programme math. pour calculer OWA
𝑥 fixé, il faut classer les 𝑓𝑠 𝑥 𝑠 ∈ 𝑆 par ordre décroissant
et les affecter aux 𝑠 qui eux sont déjà classés par ordre décroissant
On définit les variables binaires suivantes :
𝑦𝑖𝑗 = 1 si on affecte 𝑓𝑖 (𝑥) à 𝑗 , 0 sinon
Pour obtenir 𝑂𝑊𝐴 𝑥 = 1 𝑓 1 𝑥 +2 𝑓 2 𝑥 + ⋯ + 𝑝 𝑓 𝑝 (𝑥) ,
𝑝 𝑝
il suffit de chercher l’affectation 𝑦 qui maximise σ𝑗=1 𝑗 σ𝑖=1 𝑓𝑖 (𝑥)𝑦𝑖𝑗
En effet, pour maximiser cette somme de produits,
on affecte le plus gros au plus gros, le deuxième plus gros au deuxième plus etc ..
20
L’affectation ordonnée des poids
maximise la moyenne
Exemple :
3 critères 𝑐1 = 4, 𝑐2 = 3, 𝑐3 = 5
Critères triés 𝑐(1) = 5, 𝑐(2) = 4, 𝑐(3) = 3
Prenons 1 = 0,6 , 2 = 0,3 , 3 = 0,1
2 𝑐(1) + 1 𝑐(2) + 3 𝑐(3) = 0,3 × 5 + 0,6 × 4 + 0,1 × 3 = 4,2
1 𝑐(1) + 2 𝑐(2) + 3 𝑐(3) = 0,6 × 5 + 0,3 × 4 + 0,1 × 3 = 4,5
21
Minimiser la moyenne ordonnée
L’opération se passe en 2 temps
1. Pour x fixé, affecter les poids de façon
ordonnée pour obtenir la moyenne ordonnée
2. Ensuite, minimiser sur x la moyenne ordonnée
Exercice: écrire un PL pour calculer et minimiser
cette moyenne ordonnée
22
Programme pour calculer OWA
𝑝 𝑝
max σ𝑗=1 𝑗 σ𝑖=1 𝑓𝑖 (𝑥)𝑦𝑖𝑗
𝑦
Contraintes d’affectation
𝑝
𝑦𝑖𝑗 = 1 ∀𝑗 = 1, … , 𝑝
𝑖=1
𝑝
𝑦𝑖𝑗 = 1 ∀𝑖 = 1, … , 𝑝
𝑗=1
Les contraintes binaires 𝑦𝑖𝑗 ∈ 0,1 peuvent être relâchées en 𝑦𝑖𝑗 ≥ 0
On obtient donc pour x fixé un PL en y. Cependant on a des produits 𝑓𝑖 (𝑥)𝑦𝑖𝑗
et quand x n’est plus fixé, le programme n’est plus linéaire.
23
Programme pour calculer OWA
On prend alors le dual du problème d’affectation précédent
𝛼𝑖 variable duale associée à la contrainte d’affectation i
𝛽𝑗 variable duale associée à la contrainte d’affectation j
𝑝
min 𝛼𝑖 + 𝛽𝑖
𝛼,𝛽 𝑖=1
sous les contraintes
𝛼𝑖 + 𝛽𝑗 ≥ 𝑗 𝑓𝑖 𝑥 𝑖, 𝑗 = 1, … , 𝑝
Cette fois 𝑓𝑖 𝑥 est multiplié par une constante 𝑗
24
Programme pour minimiser OWA
Donc pour minimiser OWA, on n’a plus qu’à résoudre :
𝑝
min 𝛼𝑖 + 𝛽𝑖
𝑥, 𝛼, 𝛽 𝑖=1
sous les contraintes
𝛼𝑖 + 𝛽𝑗 ≥ 𝑗 𝑓𝑖 𝑥 𝑖, 𝑗 = 1, … , 𝑝
ቊ
𝑥∈𝑋
25
Exercices
• Donner un programme mathématique (linéaire) pour calculer le plus court chemin
d’un sommet à un autre dans un graphe orienté.
• Pour un graphe avec un ensemble S de scenarios possibles sur les valeurs des arcs,
donner le programme mathématique qui calcule le chemin qui minimise
la moyenne ordonnée de la valeur des chemins.
26
Ensemble d’incertitude
27
Ensemble d’incertitude
Scenarios sont en nombre fini
Pas toujours simple de définir un scenario
Généralisation
Chacune des données incertaines est à l’intérieur d’un intervalle donné
Donnée 𝑑ሚ ∈ 1,2 plutôt que dire 𝑑ሚ = 1 𝑜𝑢 𝑑ሚ = 2
28
Ensemble d’incertitude
Modèle Bertsimas et Sim
𝑑ሚ donnée incertaine dans un intervalle donné : 𝑑ሚ ∈ 𝑑ҧ − 𝑑,
መ 𝑑ҧ + 𝑑መ
𝑑ҧ valeur nominale
𝑑መ > 0 variation maximum autour de la valeur nominale
Soit de façon équivalente 𝑑ሚ = 𝑑ҧ + 𝑑∆
መ avec ∆∈ −1,1
∆ variable aléatoire mais on ne connait pas sa loi de probabilité
On dit simplement que toutes les données ne peuvent pas être en même temps
éloignées de leur valeurs nominales.
Seul un certain nombre pourront être différentes de leur valeur nominale.
29
Ensemble d’incertitude
Modèle Bertsimas et Sim
n données certaines 𝑑ሚ𝑖 𝑖 = 1, … , 𝑛
𝑑ሚ𝑖 = 𝑑ҧ𝑖 + 𝑑መ 𝑖 ∆𝑖 avec ∆𝑖 = −1,1
Ensemble d’incertitude
𝑛
𝐷 = ∆∈ −1,1 𝑛 : ∆𝑖 ≤
𝑖=1
30
Ensemble d’incertitude
Modèle Bertsimas et Sim
Soit 𝑑መ = 𝑠𝑢𝑝 𝑑መ 𝑖 : 𝑖 = 1, … , 𝑛
D est inclus dans la boule (fermée) centrée en le vecteur 𝑑ҧ des valeurs nominales
መ où la distance est définie par la norme 1 .
et de rayon 𝑑
𝑛 𝑛
𝑑ሚ𝑖 − 𝑑ҧ𝑖 = 𝑑መ 𝑖 ∆𝑖 ≤ 𝑑∆
መ 𝑖⇒ 𝑑ሚ𝑖 − 𝑑ҧ𝑖 ≤ 𝑑መ መ
∆𝑖 ≤ 𝑑
𝑖=1 𝑖=1
C’est-à-dire 𝑑ሚ − 𝑑ҧ 1
መ
≤ 𝑑
d2
D pour n=2 et =1
ҧ d1
𝑑
31
Contrainte avec des coefficients incertains
σ𝑛𝑖=1 𝑎 𝑖 𝑥𝑖 ≤ 𝑏 avec coefficients incertains 𝑎 𝑖 = 𝑎ത𝑖 + 𝑎ො𝑖 ∆𝑖 𝑒𝑡 ∆𝑖 ∈ −1,1
La contrainte s’écrit
𝑛 𝑛
𝑎ത𝑖 𝑥𝑖 + 𝑎ො𝑖 ∆𝑖 𝑥𝑖 ≤ 𝑏
𝑖=1 𝑖=1
On veut une solution x valable quelque soit la réalisation des coefficients dans
l’ensemble D d’incertitude.
On remplace la partie incertaine (rouge) par sa valeur maximum dans D.
𝑛
max 𝑎ො𝑖 ∆𝑖 𝑥𝑖
∆∈𝐷 𝑖=1
32
Contrainte avec des coefficients incertains
Protection contre l’incertitude : max σ𝑛𝑖=1 𝑎ො𝑖 ∆𝑖 𝑥𝑖
∆∈𝐷
Pour maximiser, si 𝑥𝑖 > 0 on prend ∆𝑖 ≥ 0 et si 𝑥𝑖 < 0 on prend ∆𝑖 ≤ 0
Donc ∆𝑖 𝑥𝑖 = ∆𝑖 𝑥𝑖
σ𝑛𝑖=1 ∆𝑖 ≤
La protection se réécrit : max σ𝑛𝑖=1 𝑎ො𝑖 ∆𝑖 𝑥𝑖 𝑠. 𝑐. ൝
∆ ∆𝑖 ∈ −1,1 𝑖 = 1, … , 𝑛
σ𝑛𝑖=1 𝑧𝑖 ≤
Soit en posant 𝑧𝑖 = ∆𝑖 : max σ𝑛𝑖=1 𝑎ො𝑖 𝑧𝑖 𝑥𝑖 𝑠. 𝑐. ൝
𝑧 𝑧𝑖 ∈ 0,1 𝑖 = 1, … , 𝑛
Pour x fixé, ce programme est linéaire.
En raison des produits 𝑧𝑖 𝑥𝑖 , ce n’est plus le cas quand x varie.
On passe au dual.
33
Contrainte avec des coefficients incertains
σ𝑛𝑖=1 𝑧𝑖 ≤
Protection contre l’incertitude : max σ𝑛𝑖=1 𝑎ො𝑖 𝑧𝑖 𝑥𝑖 𝑠. 𝑐. ൝
𝑧 𝑧𝑖 ∈ 0,1 𝑖 = 1, … , 𝑛
𝜇 + 𝜆𝑖 ≥ 𝑎ො𝑖 𝑥𝑖 𝑖 = 1, … , 𝑛 (1)
On passe au dual. min 𝜇Γ + σ𝑛𝑖=1 𝜆𝑖 𝑠. 𝑐. ቊ
𝜇,𝜆 𝜇 ≥ 0, 𝜆𝑖 ≥ 0 𝑖 = 1, … , 𝑛 (2)
La contrainte s’écrit
σ𝑛𝑖=1 𝑎ത𝑖 𝑥𝑖 + min 𝜇Γ + σ𝑛𝑖=1 𝜆𝑖 ≤ 𝑏 avec (1), (2)
𝜇,𝜆
Maintenant si cette contrainte est dans un programme de maximisation
on peut enlever le min car les variables , se positionneront de façon à minimiser
𝜇Γ + σ𝑛𝑖=1 𝜆𝑖 afin que le problème soit moins contraint
34
Contrainte avec des coefficients incertains
Exercice 1.
On considère un problème de sac-à-dos en variables binaires. Les poids des objets
sont incertains.
On veut une solution qui maximise la valeur du sac et robuste par rapport à l’incertitude.
En supposant qu’au plus poids vont dévier de leur valeur nominale, donner le PL en 0-1
qui donne une telle solution.
Même question en supposant maintenant que ce sont les utilités des objets qui sont
incertaines
Exercice 2.
Montrer que si les données incertaines sont dans l’objectif, on peut toujours se ramener
au cas d’incertitude sur une contrainte
35
Contrainte avec des coefficients incertains
Garantie en probabilité
Bertsimas et Sim ont donné une borne sur la probabilité que la contrainte incertaine
soit violée
Si les var. aléatoires 𝑎 𝑖 sont indépendantes
Si 𝑎 𝑖 est symétriquement distribué de part et d’autre de sa valeur nominale 𝑎ത𝑖 i
Si 𝑥 ∗ est une solution satisfaisant la contrainte protégée avec le paramètre
𝑛 ∗ 2
𝑃𝑟𝑜𝑏𝑎 𝑎 𝑖 𝑥𝑖 > 𝑏 ≤ 𝑒𝑥𝑝 −
𝑖=1 2𝑛
[Link] and [Link]. The price of robustness. Operations Research 52(1): 35-53 (2004)
36
Programmation robuste avec recours
37
Programmation robuste avec recours
2 niveaux de décision
Niveau 1 : décision que l’on prend maintenant
Niveau 2 : décision que l’on prendra plus tard une fois les données révélées
min 𝑐𝑥 + 𝑄(𝑥)
𝑥∈𝑋
où 𝑄 𝑥 = max min 𝑞𝑦: 𝐴𝑥 + 𝐵𝑦 ≤ ℎ
𝑦
où = 𝑞, 𝐴, 𝐵, ℎ représente les données incertaines
𝑥 décision de niveau 1
𝑦 décision de niveau 2 (variables de recours)
𝑄 𝑥 est le problème de recours. Il dépend des décisions prises au niveau 1
38
Exemple
On doit construire un réseau afin d’aller d’un point à un autre par le plus court chemin.
Mais les valeurs de parcours des arcs sont incertaines
2 1
5
3 Coûts de construction des arcs
1
1 0
10 4
Plus court chemin de 1 à 4
2 (3 , 0)
(0 , 1)
3 2 scenarios sur la valeur des arcs
(0 , 3)
1 (2 , 0)
(3 , 2) 4
39
Exemple
On doit construire un réseau afin d’aller d’un point à un autre par le plus court chemin.
Mais les valeurs de parcours des arcs sont incertaines
2 1
5
3 Décision maintenant
1
1 0 Variables x construction du réseau
10 4 Quels arcs construit-on ?
Plus court chemin de 1 à 4
2 scenarios sur la valeur des arcs
2 (3 , 0)
(0 , 1) Pour chaque scenario s, il y a les
3
(0 , 3) variables de recours ys qui représentent les
1 (2 , 0) arcs parcourus dans le plus court chemin
(3 , 2) 4
40
Exemple
2
5
Si je construis ce réseau coût = 16
1
1
10 4
Plus court chemin de 1 à 4 2 scenarios sur la valeur des arcs
Pour chaque scenario
Sc.1 : plus court chemin 1-2-4 valeur=0
2 Sc.2 : plus court chemin 1-4 valeur=2
(0 , 1)
(0 , 3)
1
4 Le coût de cette solution est (au pire) 16+max{0,2}=18
(3 , 2)
41
2 1 2 (3 , 0)
5 (0 , 1)
3 3
1 (0 , 3)
1 0 1 (2 , 0)
10 4 (3 , 2) 4
réseau Coût de Sc.1 plus Sc.2 plus Val. max Cout total
constru court court pour aller constructio
ction chemin chemin de 1 à 4 n + max
plus court
de 1 à 4 de 1 à 4 chemin
1-2-3-4 6 5 1 5 11
1-2-4 6 0 4 4 10
1-4 10 3 2 3 13
1-2-3-4 2-4 7 0 1 1 8 Sol. opt.
1-2-3-4 1-4 16 3 1 3 19
1-2-4 1-4 16 0 2 2 18
1-2-3-4 2-4 17 0 1 1 18
1-4
42
Commentaires de la solution
La solution optimale robuste est le graphe formé des arcs 1-2-3-4 et 2-4
Cette solution ne coutera jamais plus de 8 (tenant compte du chemin de 1 à 4)
2 1
5
3 Solution robuste
1
1 0
4
- Si on savait que c’est le scenario 1 qui va se réaliser alors on prendrait
la solution formée par le graphe 1-2-4 de coût total 6 (avec chemin de 1 à 4)
- Si on savait que c’est le scenario 2 qui va se réaliser alors on prendrait
la solution formée par le graphe 1-2-3-4 de coût total 7 (avec chemin de 1 à 4)
Dans les 2 cas, c’est inférieur à 8, bien sûr, mais pas très éloigné.
2 2 1
5 Sc.1 5 Sc.2
3
1
1 1 0
4 4
Par contre,
- si on choisissait le graphe 1-2-4 et si le scenario 2 se réalisait : coût total 10
- si on choisissait le graphe 1-2-3-4 et si le scenario 1 se réalisait : coût total 11
Ces 2 solutions coûteront plus que 8. 43
Programmation avec recours assoupli
On peut « assouplir » le problème de recours
Au lieu de minimiser le pire scenario
on minimise la moyenne ordonnée OWA des scenarios
min 𝑐𝑥 + 𝑄(𝑥)
𝑥∈𝑋
où 𝑄 𝑥 = OWA min 𝑞𝑦: 𝐴𝑥 + 𝐵𝑦 ≤ ℎ
𝑦
où = 𝑞, 𝐴, 𝐵, ℎ représente les données incertaines
44
Exemple recours avec OWA
2 0
5
3 Coûts de construction des arcs
1
1 0
10 4
Plus court chemin de 1 à 4
2 (3 , 0)
(0 , 1)
3 2 scenarios sur la valeur des arcs
(4 , 3)
1 (4 , 2)
(3 , 2) 4
45
2 0 2 (3 , 0)
5 (0 , 1)
3 3
1 (4 , 3)
1 0 1 (4 , 2)
10 4 (3 , 2) 4
réseau Coût Sc.1 Sc.2 Val. max Cout OWA de Cout
de plus plus sc.1 et 2 total sc.1 et 2 total
const court court pour construct avec construct
ructi ion + max ion +
on
chemin chemin aller de plus
1=2=½ OWA
de 1 à 4 de 1 à 4 1à4 court
chemin
1-2-3-4 5 7 3 7 12 5 10
1-2-4 6 4 4 4 10 4 10
1-4 10 3 2 3 13 2,5 12,5
1-2-3-4 2-4 6 4 3 4 10 3,5 9,5 [Link].
1-2-3-4 1-4 15 3 2 3 18 2,5 17,5
1-2-4 1-4 16 3 2 3 19 2,5 18,5
1-2-3-4 2-4 16 3 2 3 19 2,5 18,5
1-4 46
Modèle mathématique pour programmation
robuste avec recours
S ensemble de scenarios
On met une variable y par scenario
𝛾 représente la valeur Q(x) du problème de recours
𝛾 ≥ max 𝑞 𝑠 𝑦 𝑠
𝑠=1,…, 𝑆
min 𝑐𝑥 + 𝛾
𝑥,𝛾,𝑦
𝐴𝑠 𝑥 + 𝐵 𝑠 𝑦 𝑠 ≤ ℎ 𝑠 𝑠 = 1, … , 𝑆
s.c. ቐ𝛾 ≥ 𝑞 𝑠 𝑦 𝑠 𝑠 = 1, … , 𝑆
𝑥∈𝑋
47
Modèle mathématique pour programmation
robuste avec recours OWA
S ensemble de scenarios
On met une variable y par scenario
𝑆
σ𝑠=1 𝛼𝑠 + 𝛽𝑠 représente la valeur OWA(x) (moyenne ordonnée des scénarios)
𝛼𝑠 + 𝛽𝑠′ ≥ 𝑠′ × 𝑞 𝑠 𝑦 𝑠 contraintes pour construire OWA
𝑠 𝑠 = 1, … , 𝑆 sont les poids choisis pour la moyenne ordonnée
𝑆
min 𝑐𝑥 + 𝛼𝑠 + 𝛽𝑠
𝑥,𝛼,𝛽,𝑦 𝑠=1
𝐴𝑠 𝑥 + 𝐵 𝑠 𝑦 𝑠 ≤ ℎ 𝑠 𝑠 = 1, … , 𝑆
s.c. ቐ𝛼𝑠 + 𝛽𝑠′ ≥ 𝑠′ × 𝑞 𝑠 𝑦 𝑠 𝑠, 𝑠 ′ = 1, … , 𝑆
𝑥∈𝑋
48
Remarque sur la modélisation des problèmes robustes
avec ou sans recours
Programmation robuste sans recours min 𝛾
min max 𝑓𝑠 (𝑦) 𝛾,𝑦
𝑦 𝑠∈𝑆 s.c. 𝛾 ≥ 𝑓𝑠 𝑦 ∀𝑠 ∈ 𝑆
min 𝛾
Programmation robuste avec recours: 𝛾,𝑦 𝑠 𝑠∈𝑆
problème de recours s.c. 𝛾 ≥ 𝑓𝑠 𝑦 𝑠 ∀𝑠 ∈ 𝑆
max min 𝑓𝑠 (𝑦)
𝑠∈𝑆 𝑦
Dans le 1er cas : un y pour tous les scenarios
Dans le 2ème cas : un ys par scenario
49
Exemple
Plus court chemin de 1 à 4
2 scenarios sur longueurs des arcs
2 (3 , 0)
(0 , 1)
3
(0 , 3)
1 (2 , 0)
(3 , 2) 4
sc. 1 sc. 2 max
ch. 1-2-3-4 5 1 5
ch. 1-2-4 0 4 4
ch. 1-4 3 2 3 minch max
min 0 1
maxsc min
min max : y = ch. 1-4
max min : ysc1 = ch. 1-2-4, ysc2 = ch. 1-2-3-4
50
Problème robuste avec recours K-adaptable
On partitionne l’ensemble d’incertitude (ou les scenarios) en K sous-ensembles S1,…,SK
Et on prend une variable de recours par sous-ensemble Sk
Les 2 cas extrêmes:
K=1 c’est le problème robuste (pas de recours)
K=|S| c’est le problème robuste avec recours (total)
min 𝛾
𝛾,𝑦 𝑘 𝑘=1,…,𝐾
s.c. 𝛾 ≥ 𝑓𝑠 𝑦 𝑘 ∀𝑠 ∈ 𝑆 𝑘 , 𝑘 = 1, … , 𝐾
Pour chaque scenario 𝑠 ∈ 𝑆 𝑘 on prendra la même décision 𝑦 𝑘
D. Bertsimas, C. Caramanis. Finite adaptabilty in multistage linear optimisation
IEEE Transactions in Automatic Control, Vol. 55 (2), p.2751-2766 (2010)
51
Exercices
• Modéliser le problème de la construction de réseau robuste avec recours
• Modéliser le problème de la construction de réseau robuste avec recours
assoupli par OWA
par des programmes linéaires en nombres entiers PLNE
52
Références
[Link] and [Link]. The price of robustness. Operations Research 52(1): 35-53 (2004)
D. Bertsimas, C. Caramanis. Finite adaptabilty in multistage linear optimisation
IEEE Transactions in Automatic Control, Vol. 55 (2), p.2751-2766 (2010)
Cédric Hervet. Thèse de l’Ecole Polytechnique en Mathématiques Appliquées
Optimization of Optical Network Deployment. Considerations on demand uncertainty
Soutenue le 18 Décembre 2013
53
Modèles en AMPL
54
modèle prog. robuste avec recours en AMPL
# programmation robuste avec recours
# construction d'un reseau pour aller d'un sommet depart vers une arrivee
# couts construction connus
# incertitude sur les couts de parcours des arcs sous forme de scenarios
#
# variable x selection arcs pour construction du reseau
# variable y parcours des arcs dans le plus court chemin
#
param nb_som; # nbre sommets du graphe
param nb_scen;# nbre scen des couts de parcours
param d{i in 1..nb_som}; # demandes
param E{i in 1..nb_som,j in 1..nb_som}; # matrice adjacence du graphe
param c{i in 1..nb_som,j in 1..nb_som}; # cout construction
param q{i in 1..nb_som,j in 1..nb_som,k in 1..nb_scen}; # cout parcours arcs
#
# variables
#
var x{i in 1..nb_som,j in 1..nb_som} binary; # choix arc a construire
var y{i in 1..nb_som,j in 1..nb_som,k in 1..nb_scen} >=0, integer;
var gamma;
#
# modele
#
minimize f:sum{i in 1..nb_som,j in 1..nb_som}E[i,j]*c[i,j]*x[i,j]+gamma;
# contraintes
contr_flot{i in 1..nb_som,k in 1..nb_scen}:
sum{j in 1..nb_som}E[j,i]*y[j,i,k]-sum{j in 1..nb_som}E[i,j]*y[i,j,k]=d[i];
contr_gamma{k in 1..nb_scen}:
gamma>=sum{i in 1..nb_som,j in 1..nb_som}E[i,j]*q[i,j,k]*y[i,j,k];
contr_construction{i in 1..nb_som,j in 1..nb_som:E[i,j]<>0}:
sum{k in 1..nb_scen}y[i,j,k]<=nb_scen*x[i,j]; # on ne peut utiliser que arc construit 55
modèle prog. robuste avec recours – les DATA en AMPL
param nb_som:=4;
param nb_scen:=2;
# matrice adjacence du graphe
param E: 1 2 3 4 :=
1 0101
2 0011
3 0001
4 0000
;
# demande pour definir sommet depart -1 et arrivee +1
param d:=
1 -1
2 0
3 0
4 1;
# cout construction
param c: 1 2 3 4:=
1 0 5 0 10
2 0011
3 0 0 0 0.0
4 0000
;
# couts de parcours des arcs
param q:=
[*,*,1] : 1 2 3 4 :=
1 0 0.0 0 3
2 0 0 3 0.0
3 0002
4 0000
[*,*,2] : 1 2 3 4 :=
1 0102
2 0 0 0.0 3
3 0 0 0 0.0
4 0000
;
56
Modèle prog. robuste avec recours OWA en AMPL
# programmation robuste avec recours assouplie avec OWA (moyenne ordonee)
# construction d'un reseau pour aller d'un sommet depart vers une arrivee
# couts construction connus
# incertitude sur les couts de parcours des arcs sous forme de scenarios
#
# variable x selection arcs pour construction du reseau
# variable y parcours des arcs dans le plus court chemin
#
param nb_som; # nbre sommets du graphe
param nb_scen;# nbre scen des couts de parcours
param d{i in 1..nb_som}; # demandes
param E{i in 1..nb_som,j in 1..nb_som}; # matrice adjacence du graphe
param c{i in 1..nb_som,j in 1..nb_som}; # cout construction
param q{i in 1..nb_som,j in 1..nb_som,k in 1..nb_scen}; # cout parcours arcs
param lambda{k in 1..nb_scen};
#
# variables
#
var x{i in 1..nb_som,j in 1..nb_som} binary; # choix arc a construire
var y{i in 1..nb_som,j in 1..nb_som,k in 1..nb_scen} >=0, integer;
var alpha{k in 1..nb_scen};
var beta{k in 1..nb_scen};
#
# modele
#
minimize f:
sum{i in 1..nb_som,j in 1..nb_som}E[i,j]*c[i,j]*x[i,j]+sum{k in 1..nb_scen}(alpha[k]+beta[k]);
# contraintes
# flot
contr_flot{i in 1..nb_som,k in 1..nb_scen}:
sum{j in 1..nb_som}E[j,i]*y[j,i,k]-sum{j in 1..nb_som}E[i,j]*y[i,j,k]=d[i];
# contrainte pour calculer OWA
contr_OWA{k in 1..nb_scen,k_pr in 1..nb_scen}:
alpha[k]+beta[k_pr]>=lambda[k_pr]*sum{i in 1..nb_som,j in 1..nb_som}E[i,j]*q[i,j,k]*y[i,j,k];
# on ne peut passer par un arc i,j que s'il est construit
contr_construction{i in 1..nb_som,j in 1..nb_som:E[i,j]<>0}:
sum{k in 1..nb_scen}y[i,j,k]<=nb_scen*x[i,j];
57
Modèle prog. robuste avec recours OWA – les DATA en AMPL
param nb_som:=4;
param nb_scen:=2;
# on doit avoir lambda[1]>=lambda[2]>=... et la somme =1
param lambda:=
1 0.75
2 0.25
;
# matrice adjacence du graphe
param E: 1 2 3 4 :=
1 0101
2 0011
3 0001
4 0000
;
# demande pour definir sommet depart -1 et arrivee +1
param d:=
1 -1
2 0
3 0
4 1;
# cout construction
param c: 1 2 3 4:=
1 0 5 0 10
2 0 0 0.0 1
3 0 0 0 0.0
4 0000
;
# couts de parcours des arcs
param q:=
[*,*,1] : 1 2 3 4 :=
1 0 0.0 0 3
2 0034
3 0004
4 0000
[*,*,2] : 1 2 3 4 :=
1 0102
2 0 0 0.0 3
3 0002
4 0000
;
58