Décomposition de Benders; cas linéaireferland/ift6504/contenu_cours/Relaxation... · La...

Décomposition de Benders;

cas linéaire

( ) ( )( )

T

La décomposition de Benders est bien adapté pour solutionnerdes problèmes comportant des variables contrariantes.

Considérons le problème typique suivant Min

Sujet à,

o0

ù ,

P

b

f y

F y

y

c x

Ax

xx

Yc

+

∈− ≥

≥∈

( ) ( ) ( )

1 21

T

1

, , est une matrice , est une fonctionà valeurs réelles, et , , est un vecteur de

fonctions à valeurs réelles.

n n

m

R y R A m n f

F y f y f y

m

∈ ×

= …

Les sont à traiter dans le sens où elles apparissent linéairement dans le problème, ce qui n'est pasnécessairement le cas p v

variables faciles

ariables contrariou anr les .tes

x

y

Par exemple les variables peuvent être contraintes à prendre des valeurs entières, et alors nous avons un problème de programmation linéaire mixte si les fonctions , et sont linéaires.

y

f F

Problème équivalent

( ) ( )( )

( )

T

Hypo

Déter

thèse

minons d'abord un problème équivalent àMin

Sujet à, .

. La matrice est de plein rang. possède une solution optim

s

ale fi e

0

ni .

:

f y

F y

y

P

b

i Aii P

c x

Ax

Yx

+

− ≥∈≥

( )( )

( ) ( ) ( ){ }{ }1

T

1 0

de sur l'espace des variables contrariantes pourgénérer le problème equivalent :

Min

Projec

Min :

tion

y Y x

P

EP

EP f y c x Ax F y b∈ ≥

+ ≥ +

( )( )

( ) ( ) ( ){ }{ }1

T

1 0

de sur l'espace des variables contrayantes pourgénérer le problème equivalent :

Min

Projec

Min :

tion

y Y x

P

EP

EP f y c x Ax F y b∈ ≥

+ ≥ +

( ){ }Dénotons par

= : il existe au moins un 0 tel que .y x Ax F y bΓ ≥ ≥ +

( )( )

* *

*

Puisque par l'hypothèse . il existe une solution optimale ,de , alors il s'ensuit que . Ainsi .

ii x y

P y Y Y∈ Γ Γ ≠ Φ∩ ∩

( ){ }

( ){ }T

0

De plus, puisque pour tout , : , 0 ,

alors pour ces valeurs de , par conventionMin : .

x

y

x Ax F y b x

y

c x Ax F y b≥

∉Γ≥ + ≥ = Φ

∉Γ≥ + = ∞

( )( )

( ) ( ) ( ){ }{ }1

T

1 0

de sur l'espace des variables contrayantes pourgénérer le problème equivalent :

Min

Projec

Min :

tion

y Y x

P

EP

EP f y c x Ax F y b∈ ≥

+ ≥ +

( ){ }

( ){ }T

0

De plus, puisque pour tout , : , 0 ,

alors pour ces valeurs de , par conventionMin : .

x

y

x Ax F y b x

y

c x Ax F y b≥

∉Γ≥ + ≥ = Φ

∉Γ≥ + = ∞

( ) ( )( )

( ) ( ) ( ){ }{ }

1 2

T

2 0

Ainsi il n'y a pas de perte de généralité de restreindre à appartenir à Γ dans . Donc le problème suivant est équivalent à :

Min Min : .y Y x

yEP EP

P

EP f y c x Ax F y b∈ Γ ≥

+ ≥ +∩

Pour une valeur fixée de , considérons la paire de problèmesprimal-dual suivante:

y

( )( )

TMin sujet à

0

yP c x

Ax F y b

x

≥ +≥

( ) ( )( )T

T

Max Sujet à

0

yD F y b u

A u cu

+

≤≥

{ }( )

( )

T

* *

*

Notons d'abord que le domaine réalisable du dual n'est pas vide.: : , 0 .En effet, puisque qu'il existe une solution optimale , de

,alors est solution optimal d

u A u c u

x y

P x

≤ ≥ ≠ Φ

*u primal lorsque .Par le théorème de dualité en programmation linéaire, il s'ensuitque le dual possède une solution optimale.

y y=

( ) ( ) ( ){ }{ }T

2 0 Min Min :

y Y xEP f y c x Ax F y b

∈ Γ ≥+ ≥ +

∩

Pour une valeur fixée de , considérons la paire de problèmesprimal-dual suivante:

y

( )( )

TMin sujet à

0

yP c x

Ax F y b

x

≥ +≥

( ) ( )( )T

T

Max Sujet à

0

yD F y b u

A u cu

+

≤≥

{ }T

Appliquons le théorème de Goldman au domaine réalisable du dual: : , 0 ,et puisque par hypothèse, la matrice est de plein rang

est l'enveloppe convexe des points

u A u c u K C

AK

≤ ≥ = +

=

{ }{ }

T

T

extrêmes de: , 0

: 0, 0 .u A u c u

C u A u u

≤ ≥

= ≤ ≥

{ }T

Appliquons le théorème de Goldman au domaine réalisable du dual: : , 0 ,et puisque par hypothèse, la matrice est de plein rang

est l'enveloppe convexe des points

u A u c u K C

A

K

≤ ≥ = +

=

{ }{ }

T

extrêmes de: , 0

: 0, 0 .T

u A u c u

C u A u u

≤ ≥

= ≤ ≥

{ } { }{ }

1 T

1

Soient

, , l'ensemble des points extrêmes de : , 0

, , l'ensemble des générateurs du cône

p

q

u u u A u c u

v v C

≤ ≥…

…

{ }{ }

T

est l'enveloppe convexe des points extrêmes de: , 0

: 0, 0 .T

K

u A u c u

C u A u u

=≤ ≥

= ≤ ≥

{ } { }{ }

1 T

1

Soient

, , l'ensemble des points extrêmes de : , 0

, , l'ensemble des générateurs du cône

p

q

u u u A u c u

v v C

≤ ≥…

…

{ }T

1 1

11

1 q

Par conséquent, si : , 0 , alors

, , ,ou encore

où

1 , , , 0

, , 0

p qj j

j j

j j

p

j p

j

u u A u c u

u z t z K t C

u u vα β

α α α

β β

= =

=

∈ ≤ ≥

= + ∈ ∈

= +

= ≥

≥

∑ ∑

∑ …

…

{ }1

Contraintes équivalentes à la condition spécifiées en

termes des générateurs du cône , , q

y

v v

∈Γ

…

( ) ( )( )T

Pour n'importe laquelle valeur de ,

borné 0supérieurement

Théorème

,

1

1,

.j

y

y

D F y b v

j q

+ ≤⇔ ∀ = …

( ) ( )( )T

T

Max Sujet à

0

yD F y b u

A u cu

+

≤≥

( )

( )( )T

Procédons par contradiction pour démontrerla nécessité des conditions. Pour ce faire, supposons qu'il existe

un indice , 1

Preuve. nécessit

, tel q e

é

u 0.kk k q F y b v≤ ≤ + >

( )Considérons une solution quelconque du problème .

Alors .yu D

u z t= +

( )T T

Il est facile de vérifier que pour tout 0,

puisque 0, 0, 0, 0 .

k

k k

t v C

A v A t v t

λ

λ

λ λ

≥

+ ∈

≤ ≤ ≥ ≥

( ) ( )( )T

Pour n'importe laquelle valeur de ,

borné 0supérieurement

Théorème

,

1

1,

.j

y

y

D F y b v

j q

+ ≤⇔ ∀ = …

( ) ( )( )T

T

Max Sujet à

0

yD F y b u

A u cu

+

≤≥

( )Preuve. nécessité

( )Considérons une solution quelconque du problème .

Alors .yu D

u z t= +

( )T T

Il est facile de vérifier que pour tout 0,

puisque 0, 0, 0, 0 .

k

k k

t v C

A v A t v t

λ

λ

λ λ

≥

+ ∈

≤ ≤ ≥ ≥

( )

( )( ) ( ) ( )( ) ( )( )

( )

T T T

Par conséquent est une solution réalisable de .

Mais la valeur de la fonction économique du dual devient

,

une contradiction puisque par hypothèse, est borné.

ky

k k

y

z t v D

F y b u v F y b u F y b v

D

λ

λ

λ λ→∞

+ +

+ + = + + + → ∞

( ) ( )( )T

T

Max Sujet à

0

yD F y b u

A u cu

+

≤≥

( )

1 1

1 1 q1

La suffisance des conditions est vérifiée par simplessubstitutions. En effet

où 1 , , , , , , 0.

suffi

sa ce

n

p qj j

j j

j j

p

j p

j

u z t u vα β

α α α β β

= =

=

= + = +

= ≥

∑ ∑

∑ … …

( )( ) ( )( ) ( )( )

( )( )

( )( )

T T T

1 1

T

1T

Alors

puisque 0, 0,

1, ,

p qj j

j j

j j

pj

j

j

jj

F y b u F y b u F y b v

F y b u

F y b v

j q

α β

α

β

= =

=

+ = + + +

≤ +

+ ≤ ≥

=

∑ ∑

∑

…

( ) ( )( )T

T

Max Sujet à

0

yD F y b u

A u cu

+

≤≥

( )( ) ( )( ) ( )( )

( )( )

( )( )

T T T

1 1

T

1T

Alors

puisque 0, 0,

1, ,

p qj j

j j

j j

pj

j

j

jj

F y b u F y b u F y b v

F y b u

F y b v

j q

α β

α

β

= =

=

+ = + + +

≤ +

+ ≤ ≥

=

∑ ∑

∑

…

( )( ){ }1

T

1, ,où Max .

p

j

j

j

j p

M M

M F y b u

α=

=

≤ =

= +

∑

…□

{ } ( )( )T

Corollaire 2:

0 .1, ,

jF y b v

yj q

+ ≤∈Γ ⇔ ∀ = …

( )

( )( )T

Procédons par contradiction pour démontrerla nécessité des conditions. Pour ce faire, supposons qu'il existe

un indice , 1

Preuve. nécessit

, tel q e

é

u 0.kk k q F y b v≤ ≤ + >

( )Par le théorème 1, il s'ensuit que n'est pas borné supérieurement.yD

( )Mais alors, par le théorème de dualité forte en programmation

linéaire, n'est pas réalisable et .yP y ∉Γ

{ } ( )( )T

Corollaire 2:

0 .1, ,

jF y b v

yj q

+ ≤∈Γ ⇔ ∀ = …

( )

( )( )( )

T

Pour démontrer la suffisance des conditions

supposons que 0, 1, , . Par le

théorème 1, il s'en

Preuve.

suit que est borné supérieuremen

suffisance

t.

j

y

F y b v j q

D

+ ≤ = …

( ) ( )Ainsi, puisque est réalisable, alors possède une solution

optimale.y yD D

( )Par le théorème de dualité forte en programmation linéaire, il

s'ensuit que possède également une solution optimale

finie, et .yP

y ∈Γ □

( ) ( ) ( ){ }{ }

{ } ( )( )

T2

0

T

à partir de

Min Min :

en utilisant le corollaire 2

0 .1, ,

po

Poursuivons la dérivation du problème équi

ur remplacer la contraint

valen

e par n

t

u

y Y x

j

EP f y c x Ax F y b

F y b vy

j q

y

∈ Γ ≥+ ≥ +

+ ≤∈Γ ⇔ ∀ =

∈Γ

∩

…

ensemble de contraintes explicitement spécifiées en termes des générateurs du cône

( ) ( ) ( ){ }{ }

( )( )

T3

0

T

Min Min :

Sujet à 0, 1, ,

y Y x

j

EP f y c x Ax F y b

F y b v j q

∈ ≥+ ≥ +

+ ≤ = …

( ) ( ) ( ){ }{ }

( )( )

T3

0

T

Min Min :

Sujet à 0, 1, ,

y Y x

j

EP f y c x Ax F y b

F y b v j q

∈ ≥+ ≥ +

+ ≤ = …

( )

( )( )T

Maintenant, se rapportant à la preuve du corollaire 2,

possède une solution optimale finie lorsque les conditions

0

1, ,sont vérifiées.

y

j

D

F y b v

j q

+ ≤ ∀ = …

( ){ } ( )( ){ }TT T

0 0

Alors, dans ce cas, par le théorème de dualité forte en programmation linéaire,

Min : Max : .x u

c x Ax F y b F y b u A u c≥ ≥

≥ + = + ≤

( ) ( ) ( ){ }{ }

( )( )

T3

0

T

Min Min :

Sujet à 0, 1, ,

y Y x

j

EP f y c x Ax F y b

F y b v j q

∈ ≥+ ≥ +

+ ≤ = …

( ){ } ( )( ){ }TT T

0 0

Alors, dans ce cas, par le théorème de dualité forte en programmation linéaire,

Min : Max : .x u

c x Ax F y b F y b u A u c≥ ≥

≥ + = + ≤

( )

( ) ( ) ( )( ){ }{ }( )( )

3

T T4

0

T

Ainsi, devient

Min Max :

Sujet à 0, 1, ,

y Y u

j

EP

EP f y F y b u A u c

F y b v j q

∈ ≥+ + ≤

+ ≤ = …

( )

( ) ( ) ( )( ){ }{ }( )( )

3

T T4

0

T

Ainsi, devient

Min Max :

Sujet à 0, 1, ,

y Y u

j

EP

EP f y F y b u A u c

F y b v j q

∈ ≥+ + ≤

+ ≤ = …

( )( ){ } ( )( ){ }T TT

1, ,0

De plus, lorsque , alors

Max : Max .j

j pu

y

F y b u A u c F y b u=≥

∈Γ

+ ≤ = +…

( )

( ) ( ) ( )( ){ }{ }( )( )

4

T

51, ,

T

Ainsi, devient

Min Max

Sujet à 0, 1, ,

j

y Y j p

j

EP

EP f y F y b u

F y b v j q

∈ =+ +

+ ≤ =

…

…

( )

( ) ( ) ( )( ){ }{ }( )( )

4

T

51, ,

T

Ainsi, devient

Min Max

Sujet à 0, 1, ,

j

y Y j p

j

EP

EP f y F y b u

F y b v j q

∈ =+ +

+ ≤ =

…

…

( ) ( ){ }

( )( ){ }( )( )

6 0

T0

1, ,T

Min

Sujet à Max

0, 1, ,

y Y

j

j p

j

EP f y y

F y b u y

F y b v j q

∈

=

+

+ =

+ ≤ =

…

…

( )0 4En utilisant une variable fictive , peut s'écrirey EP

( ) ( ){ }

( )( ){ }( )( )

6 0

T0

1, ,T

Min

Sujet à Max

0, 1, ,

y Y

j

j p

j

EP f y y

F y b u y

F y b v j q

∈

=

+

+ =

+ ≤ =

…

…

( )0

6

Puisque apparait dans la fonction économique à minimiser, le problème peut également s'écrire

y

EP

( ) ( ){ }

( )( ){ }( )( )

7 0

T0

1, ,T

Min

Sujet à Max

0, 1, ,

y Y

j

j p

j

EP f y y

F y b u y

F y b v j q

∈

=

+

+ ≤

+ ≤ =

…

…

( ) ( ){ }

( )( ){ }( )( )

7 0

T0

1, ,T

Min

Sujet à Max

0, 1, ,

y Y

j

j p

j

EP f y y

F y b u y

F y b v j q

∈

=

+

+ ≤

+ ≤ =

…

…

Finalement, nous obtenons le problème équivalent suivant:

( ) ( ){ }

( )( )( )( )

0

T

0T

Min

Sujet à , 1, ,

0, 1, ,

y Y

j

j

EP f y y

F y b u y j p

F y b v j q

∈+

+ ≤ =

+ ≤ =

…

…

Méthode de résolution de Benders

( ) ( ){ }

( )( )( )( )

0

T

0T

Dans la méthode de résolution de Benders, le problème équivalent Min

Sujet à , 1, ,

0, 1, ,

est résolu avec l'approche de relaxation.

y Y

j

j

EP f y y

F y b u y j p

F y b v j q

∈+

+ ≤ =

+ ≤ =

…

…

( ) ( ){ }

( )( )( )( )

0

T0

T

Min

Sujet à , 1, ,

0, 1, ,

y Y

j

j

EP f y y

F y b u y j p

F y b v j q

∈+

+ ≤ =

+ ≤ =

…

…

( )

{ }1 T

Déterminer une première relaxation de en

identifiant un point extrême de : , 0 (en

utilisant une phase I du

Initialisation

simplexe par exemple).

. EP

u u A u c u≤ ≥

Soit =1, =0. Aller à l'étape 1.µ ϕ

( )

( ) ( ){ }

( )( )( )( )

0

T

0T

Résoudre la relaxation de

Mi

Étape

n

Sujet à , 1, ,

0 ,

, ,

1.

1

y Y

j

j

EP

EP f y y

F y b u y j

F y b v j

µϕ

µ

ϕ

∈+

+ ≤ =

+ ≤ =

…

…

( )si ou 0, alors il n'y a pas de contraintes du type correspondantµ ϕ =

( )0Soit , une solution optimale de .y y Y EPµϕ∈

( )

( )0Étape 2. Mécanisme pour vérifier si , est ré

Résoudre le

alisable

problème

po

dual

u .

:

r

y

y y E

D

P

( ) ( )( )T

T

Max Sujet à

0

yD F y b u

A u cu

+

≤≥

( )

( )( )T

)

Par le théorème 1, il existe au moins une contrainte du deuxièmetype qui est violée:

Si n'est pas borné su

0 pour un certain ,

périeu

1, ,

re n

.

me t

j

yi

F y b j j

D

v q+ > = …

( )Utiliser le dernier tableau du simplexe lors de la résolution de

pour générer un élement .yD v C∈ɶ

( )( )T

Augmenter de 1 en ajoutant à la relaxation la contrainte

0

et reprendre l'étape 1.

F y b v

ϕ

+ ≤ɶ

–

T Min Sujet à

0

c xAx bx

=≥

Itération où est variable d'entrée : 0

Problème non borné: 0

s s

s

x c

a•

<

≤

T T

00

B

s

R s

B B

x bx x

x

c x c x z

−

= =

= =

–

T Min Sujet à

0

c xAx bx

=≥

Itération où est variable d'entrée : 0

Problème non borné: 0

s s

s

x c

a•

<

≤

T T

00

B

s

R s

B B

x bx x

x

c x c x z

−

= =

= =

T T

Soit obtenu à partir de en augmentant de 1:

1 0 ;00

s

B s s s

s B B s

x x x

x a x b ax x c x c x c

• • − − = = ≥ = +

ɶ

ɶɶ ɶ ɶ

T Min Sujet à

0

c xAx bx

=≥

Itération où est variable d'entrée : 0

Problème non borné: 0

s s

s

x c

a•

<

≤

T T

00

B

s

R s

B B

x bx x

x

c x c x z

−

= =

= =

T T

Soit obtenu à partir de en augmentant de 1:

1 0 ;00

s

B s s s

s B B s

x x x

x a x b ax x c x c x c

• • − − = = ≥ = +

ɶ

ɶɶ ɶ ɶ

} ( )

( )T T T T

Soit

ˆ 1 0 1 00 0 0

ˆ 0

ˆ 0

s s

B B s B B s

b a abx x x

Ax bAx A x x

Ax b

c x c x x c x c c x c

• • − − = − = − = ≥

= ⇒ = − ==

= − = + − = <

ɶ

ɶɶ

ɶ

( )

( )0Étape 2. Mécanisme pour vérifier si , est ré

Résoudre le

alisable

problème

po

dual

u .

:

r

y

y y E

D

P

( ) ( )( )T

T

Max Sujet à

0

yD F y b u

A u cu

+

≤≥

( )

( )( )T

0

Si possède une solution optimale , mais que la valeur

optim

)

ale

,

yD ui

y b u

i

F y+ >

( )( )T

0

alors est augmenté de 1 en ajoutant à la relaxation la contrainte correspondante

.

Reprendre l'étape 1.

F y b u y

µ

+ ≤

( )

( )0Étape 2. Mécanisme pour vérifier si , est ré

Résoudre le

alisable

problème

po

dual

u .

:

r

y

y y E

D

P

( ) ( )( )T

T

Max Sujet à

0

yD F y b u

A u cu

+

≤≥

( )

( )( )T

0

Si possède une solution optimale , et que la valeur

optimale

) yD u

F y b u

iii

y+ ≤

( )0alors , est une solution réalisable et optimale de .y y EP

( )

( )( )T

0

Si possède une solution optimale , et que la valeur

optimale

) yD u

F y b u

iii

y+ ≤

( )0alors , est une solution réalisable et optimale de .y y EP

( )

( )( )

( )( ) ( )( ){ } ( )( )

0T

T T T

01, ,

En effet toutes les contraintes de sont satisfaites à , :

1. 0, 1, ,

2. Pour tout 1, ,

Max .

Aller à l'étape 3.

j

j j

j p

EP y y

y F y b v j q

j p

F y b u F y b u F y b u y=

∈Γ⇒ + ≤ =

=

+ ≤ + = + ≤…

…

…

( ) ( ){ }

( )( )( )( )

0

T0

T

Min

Sujet à , 1, ,

0, 1, ,

y Y

j

j

EP f y y

F y b u y j p

F y b v j q

∈+

+ ≤ =

+ ≤ =

…

…

( )

( ) ( )

( )

T

Il suffit de prendre comme étant les multiplicateurs optÉtape 3. Déterminer une solution optimal

imaux

de ou de résoudre le primal

Min Sujet à

0

e , e

.

d .

y y

x

D P

c x

A

P

x

y

F y

x

b

x

≥ +

≥

Nous appliquons directement la stratégie de relaxationoù 1 puisque l'ensemble comporte l'indice associé àN

ou

ote

à .

. V V

v u

=

ɶ

Cas convexe

( )

( )( )( )( )

1

T

0T

Si est convexe et , , , sont convexes sur , la dimention

de la relaxation peut être réduite en éliminant les

contraintes satisfaites avec inégalité:

, 1, ,

0, 1, ,

à chaqu

m

j

j

Y f f f Y

EP

F y b u y j

F y b v j

µϕ

µ

ϕ

+ < =

+ < =

…

…

…

e fois que la valeur optimale de la restriction eststrictement croissante.

Cas où n’est pas bornée inférieurement(((( ))))µϕEP

( )( )

( )0

Notons que peut ne pas être borné inférieurement si

trop de contraintes de sont relaxées. Dans ce cas, pour

obtenir quand même une solution , de à l'étape 1,

nous devo bons rner artificie

EP

EP

y y EP

µϕ

µϕ

( )le problèmllem e .ent EPµϕ

( )

T

Par exemple, si certaines contraintes spécifiant sont descontraintes de non négativité des variables ( i.e., 0), alors

le problème peut être borné artificiellement en ajoutant

la contrainte

Y

y

EP

e y

µϕ

≥

=

[ ]

2

1T 2où 1, 1 et est un scalaire suffisemment grand.

n

i

i

n

y t

e R t

=

≤

= ∈

∑

…

( )

T

Par exemple, si certaines contraintes spécifiant sont descontraintes de non négativité des variables ( i.e., 0), alors

le problème peut être borné artificiellement en ajoutant

la contrainte

Y

y

EP

e y

µϕ

≥

=

[ ]

2

1T 2où 1, 1 et est un scalaire suffisemment grand.

n

i

i

n

y t

e R t

=

≤

= ∈

∑

…

( )

2T

1

0

Quand la contrainte est active pour une grande valeur de

,

nous pouvons soupçonner que n'est pas borné inférieurement,

mais nous pouvons quand même poursuivre à l'étape 2 avec ,po

n

i

i

t

e y y t

EP

y y

µϕ

=

= =∑

ur générer une contrainte additionnelle.

( )

2T

1

0

Quand la contrainte est active pour une grande valeur de

,

nous pouvons soupçonner que n'est pas borné inférieurement,

mais nous pouvons quand même poursuivre à l'étape 2 avec ,po

n

i

i

t

e y y t

EP

y y

µϕ

=

= =∑

ur générer une contrainte additionnelle.

( )Puisque par hypothèse possède une solution optimale finie,alors cette contrainte additionnelle devient redondante à la finde la résolution.

P

Bornes inférieure et supérieure

sur la valeur optimale

( )

( )( )

0

À chaque itération de la procédure, la valeur optimale

de est une sur le valeur optimale

de

borne inférieure

.

E

f y y

P

E

LB

P

µϕ

+

De plus, puisque la procédure est une application de la stratégiede relaxation, il s'ensuit que la suite des valeurs optimales des relaxations es non décroisst ante.

( )Pour dériver une , remarquons qu'à chaque

itération où possède une solution optimale finie, alors

par la dualité forte en programmation linéaire, il existe une

soluti

borne supér

on optimal

ieure

e f

inie

yD

( )( )( )

TT

de telle que

.

yx P

c x F y b u= +

( )

( ) ( )( ) ( )( )

TT

Mais alors , est une solution réalisable de et la valeurde cette solut

borne supérieure

ion

est une sur la valeur optimale de .

c x f y F y b u f y

x y P

P

+ = + +

Malheureusement, la suite de ces valeurs n'est pas non croissanteau cours des itérations.

Dénotons par générée au coursdes itérations. Cette valeur es

lat m

plus petite borne supérieuise à jour à chaque itérat

rn.

eio

UB

( ) ( ){ }{ }T

0Min Min :

y Y xf y c x Ax F y b

∈ ≥+ ≥ +

( ) ( ){ }{ } ( )T T

0Min :

xf y c x Ax F y b f y c x

≥+ ≥ + = +

( )

( )( )

0

À chaque itération de la procédure, la valeur optimale

de est une sur le valeur optimale

de

borne inférieure

.

E

f y y

P

E

LB

P

µϕ

+

Dénotons par générée au coursdes itérations. Cette valeur es

lat m

plus petite borne supérieuise à jour à chaque itérat

rn.

eio

UB

Si alors la solution associée à la borne supérieure est -optimale.

LB BU εε

− ≤

Illustration du déroulement de la procédure de Benders.

•

••

•

•

••

∗∗

∗∗

∗∗

∗

1 2 3 4 ⋯ itération

( ) valeur optimale de

valeur de la solution ,

EP

x y

µϕ•

∗

UB

LB}ε

solution -optimaleε

Méthode de résolution de Benders

avec bornes

La variante suivante de la méthode de résolution de Benderspermet d'identifier une solution -optimale en ajoutant un critère d'arrêt basé sur

.

Les modifications apportées à la méthode originale

LBUB

ε

ε− ≤

sontindiquée ros en uge.

( ) ( ){ }

( )( )( )( )

0

T0

T

Min

Sujet à , 1, ,

0, 1, ,

y Y

j

j

EP f y y

F y b u y j p

F y b v j q

∈+

+ ≤ =

+ ≤ =

…

…

( )

{ }1 T

Déterminer une première relaxation de en

identifiant un point extrême de : , 0 (en

utilisant une phase I du

Initialisation

simplexe par exemple).

. EP

u u A u c u≤ ≥

Soit Soit =1, =0. Aller à l'étape . 1.UBµ ϕ = ∞

( )

( ) ( ){ }( )( )( )( )

0

T

0T

Résoudre la relaxation de

Min

Sujet à , 1, ,

0,

Étape

, ,

1.

1

j

j

EP

EP f y y

F y b u y j

F y b v j

µϕ

µ

ϕ

+

+ ≤ =

+ ≤ =

…

…

( )si ou 0, alors il n'y a pas de contraintes du type correspondantµ ϕ =

( )0Soit , une solution optimale de .y y Y EPµϕ∈

( ) 0Soit .Si , terminer la procédure car la solution associéeà est -optimale.

LB f y y

UB LB

UB

εε

= +

− ≤

( )

( )0Étape 2. Mécanisme pour vérifier si , est ré

Résoudre le

alisable

problème

po

dual

u .

:

r

y

y y E

D

P

( ) ( )( )T

T

Max Sujet à

0

yD F y b u

A u cu

+

≤≥

( )

( )( )T

)

Par le théorème 1, il existe au moins une contrainte du deuxièmetype qui est violée:

Si n'est pas borné su

0 pour un certain ,

périeu

1, ,

re n

.

me t

j

yi

F y b j j

D

v q+ > = …

( )Utiliser le dernier tableau du simplexe lors de la résolution de

pour générer un élement .yD v C∈ɶ

( )( )T

Augmenter de en ajoutant à la relaxation la contrainte

0

et reprendre l'étape 1.

F y b v

ϕ

+ ≤ɶ

( )

( )0Étape 2. Mécanisme pour vérifier si , est ré

Résoudre le

alisable

problème

po

dual

u .

:

r

y

y y E

D

P

( )

( )( )T

0

Si possède une solution optimale , mais que la valeur

optim

)

ale

,

yD ui

y b u

i

F y+ >

( ) ( )( ){ }T

mettre à jour la borne supérieure

Min , .UB UB f y F y b u= + +

Si , terminer la procédure car la solution associéeà la borne supérieure est -optimale.

UB LB

UB

εε

− ≤

( )( )T

0

est augmenté de 1 en ajoutant à la relaxation la contrainte correspondante

.

Repr

Autrement

endre l'étape 1.

F y b u y

µ

+ ≤

( )

( )0Étape 2. Mécanisme pour vérifier si , est ré

Résoudre le

alisable

problème

po

dual

u .

:

r

y

y y E

D

P

( ) ( )( )T

T

Max Sujet à

0

yD F y b u

A u cu

+

≤≥

( )

( )( )T

0

Si possède une solution optimale , et que la valeur

optimale

) yD u

F y b u

iii

y+ ≤

( )0alors , est une solution réalisable et optimale de .y y EP

( )

( )( )T

0

Si possède une solution optimale , et que la valeur

optimale

) yD u

F y b u

iii

y+ ≤

( )0alors , est une solution réalisable et optimale de .y y EP

( )

( )( )

( )( ) ( )( ){ } ( )( )

0T

T T T

1, ,

En effet toutes les contraintes de sont satisfaites à , :

1. 0, 1, ,

2. Pour tout 1, ,

Max .

Aller à l'étape 3.

j

j j

j p

EP y y

y F y b v j q

j p

F y b u F y b u F y b u=

∈Γ⇒ + ≤ =

=

+ ≤ + = +…

…

…

( ) ( ){ }

( )( )( )( )

0

T0

T

Min

Sujet à , 1, ,

0, 1, ,

y Y

j

j

EP f y y

F y b u y j p

F y b v j q

∈+

+ ≤ =

+ ≤ =

…

…

( )

( ) ( )

( )

T

Il suffit de prendre comme étant les multiplicateurs optÉtape 3. Déterminer une solution optimal

imaux

de ou de résoudre le primal

Min Sujet à

0

e , e

.

d .

y y

x

D P

c x

A

P

x

y

F y

x

b

x

≥ +

≥

Nous appliquons directement la stratégie de relaxationoù 1 puisque l'ensemble comporte l'indice associé àN

ou

ote

à .

. V V

v u

=

ɶ

( )( )

TMin sujet à

0

yP c x

Ax F y b

x

≥ +≥

(((( )))) (((( ))))y yP DRésoudre au lieu de à l'étape 2

( ) ( )

Souvent, une fois la valeur de fixée, le problème en possèdeune structure intéressante. Dans ce cas, il serait plus intéressant

de résoudre plutôt que à l'étape 2 afin d'en profiter.

Mais nousy y

y x

P D

( ) devons avoir un moyen de récupérer les valeurs des

variables et nécessaires pour formuler les relaxations . j ju v EPµϕ

( ) ( )( )T

T

Max Sujet à

0

yD F y b u

A u cu

+

≤≥

( ) ( )( )

TMin Sujet à

, .0

c x

A

P

bx

y

F y

yx

f

Y

+

−∈≥

≥( ) ( ) ( ){ }{ }T

1 0 Min Min :

y Y xEP f y c x Ax F y b

∈ ≥+ ≥ +

( ) ( ){ }

( )( )( )( )

0

T0

T

Min

Sujet à , 1, ,

0, 1, ,

y Y

j

j

EP f y y

F y b u y j p

F y b v j q

∈+

+ ≤ =

+ ≤ =

…

…

(((( )))) (((( ))))y yP DRésoudre au lieu de à l'étape 2

( ) ( )

Souvent, une fois la valeur de fixée, le problème en possèdeune structure intéressante. Dans ce cas, il serait plus intéressant

de résoudre plutôt que à l'étape 2 afin d'en profiter.

Mais nousy y

y x

P D

( ) devons avoir un moyen de récupérer les valeurs des

variables et nécessaires pour formuler les relaxations . j ju v EPµϕ

( )Si , la résolution de génère une solution optimale .

Se référant à la dualité forte en programmation linéaire, il s'ensuitque les multiplicateurs optimaux du simplexe sont une solution

optimale d

yy P x∈Γ

( )e . Nous pouvons donc les utiliser pour générer

une nouvelle contrainte à ajouter à la relaxation.yD

( )Si , la résolution de génère une solution optimale .

Se référant à la dualité forte en programmation linéaire, il s'ensuitque les multiplicateurs optimaux du simplexe sont une solution

optimale d

yy P x∈Γ

( )e . Nous pouvons donc les utiliser pour générer

une nouvelle contrainte à ajouter à la relaxation.yD

( )

Mais il faut remarquer que les multiplicateurs optimaux dusimplexe ne constituent pas nécessairement une solution de base

de , et par conséquent ne constituent pas nécessairement

un point extrême du yD

polytope dual.

Ainsi, une telle solution peut éventuellement s'exprimer commeune combinaison linéaire convexe d'autres solutions du polytopedual générées au cours de l'étape 2.

( )Néanmoins, la procédure converge quand même, et une telle

contrainte dans peut éventuellement devenir redondante.EPµϕ

( ) ( )Maintenant si , n'est pas réalisable et n'est pas

borné supérieurement à l'étape 2. y yy P D∉Γ

( )

( )

T

Dans ce cas, si nous resolvons , la solution optimale , ,

du problème de la phase I

Min sujet à

, , 0( étant les variables d'écart et , les variables artificielles)a une v

yP x s a

e a

Ax Is Ia F y b

x s a

s a

− + = +

≥

T

aleur positive:

0.e a >

( )( )

TMin sujet à

0

yP c x

Ax F y b

x

≥ +≥

Dénotons par le vecteurs de multiplicateurs optimaux.π

π

( )

( )

T

Dans ce cas, si nous resolvons , la soltion optimale , ,

du problème de la phase I

Min sujet à

, , 0( étant les variables d'écart et , les variables artificielles)a une va

yP x s a

e a

Ax Is Ia F y b

x s a

s a

− + = +

≥

T

leur positive:

0.e a >

Dénotons par le vecteurs de multiplicateurs optimaux.π

π

( )( )T

T

Alors est une solution optimale du dual suivant

Max

Sujet à 00.

F y b

A

I

I e

π

π

πππ

+

≤− ≤

≤

Dénotons par le vecteurs de multiplicateurs optimaux.π

( )( )T

T

Alors est une solution optimale du dual suivant

Max

Sujet à 00.

F y b

A

I

I e

π

π

πππ

+

≤− ≤

≤

T 0e a >

T

Par conséquent

0 .0

AC

π ππ

≤ ⇒ ∈≥

( )( )T T

Également, par la dualité forte en programmation linéaire

0. F y b e aπ+ = >

( )( )T

Donc nous pouvons ajouter la contrainte

0

pour générer une nouvelle relaxation où augmente de 1.

F y b π

ϕ

+ ≤

( )( )T

Donc nous pouvons ajouter la contrainte

0

pour générer une nouvelle relaxation où augmente de 1.

F y b π

ϕ

+ ≤

C'est également le cas que n'est pas nécessairement un générateurdu cône. Néanmoins, la procédure converge quand même et la contrainte correspondante peut éventuellement devenir redondante.

π

Programmation linéaire mixte

( )( ) ( ) { }T

Au départ, Benders a développé sa procédure pour résoudre des problèmes de programmation linéaire mixte; i.e., dans

, , et : 0et entiers .

P

f y c y F y Ay Y y y= = = ≥

( ) ( )( )

TMin Suj t

,0e à

.

c x

A

P

bx

y

F y

yx

f

Y

+

−∈≥

≥( ) TTMin Sujet à

0 0, ent, iers.

c y

Ay

P

A b

x

y

c

xx

+

−≥

≥≥

Observons que les hypothèses de convexité ne sont pas vérifiées dans ce cas puisque n'est pas un ensemble convexe.Y

( ) ( )( )

TMin Suj t

,0e à

.

c x

A

P

bx

y

F y

yx

f

Y

+

−∈≥

≥( ) TTMin Sujet à

0 0, ent, iers.

c y

Ay

P

A b

x

y

c

xx

+

−≥

≥≥

( ) ( )( ) ( )

Dans ce cas, et les relaxations sont des problèmes

de programmation linéaire en nombres entiers, et et

sont des problèmes de programmation linéaire.y y

EP EP

P D

µϕ

( ) { }

( )( )

T0

TT0

TT

Min

Sujet à , 1, ,

0, 1, ,

0, entier

j

j

EP c y y

A y b u y j p

A y b v j q

y

+

+ ≤ =

+ ≤ =

≥

…

…

Exemple numérique

1 2 3

1 3

2 3

1 2 3

Min 10 10 15 40 Sujet à 2 2

1, , , 0

x x x y

x x y

x x y

x x x y

+ + +

+ + ≥

+ + ≥

≥

1 2 3 1 3

0 , ,1 2 3 0 2 3

Projection sur l'espace de la variable 10 10 15 : 2 2 ,

Min 40 Min1y x x x

y

x x x x x yy

x x y≥ ≥

+ + + ≥ − + + ≥ −

( ) 1 2 3

1 3

2 3

1 2 3

Min 10 10 15

Sujet à 2 21

, , 0

yP x x x

x x y

x x y

x x x

+ +

+ ≥ −

+ ≥ −

≥

( ) ( ) ( )1 2

1

2

1 2

1 2

Max 2 2 1

Sujet à 101015

, 0

yD y u y u

u

u

u u

u u

− + −

≤

≤

+ ≤

≥

( )Domaine réalisable de yD

1 10u =

2 10u =

1 2 15u u+ =

10

10( )5,10

( )10,5 Points extrêmes0 10 10 5 0

, , , ,0 0 5 10 10

( )[ ]

T

Puisque ce domaine réalisable est borné, alors

domaine réalisable de

puisque se reduit à 0,0 . est l'enveloppe convexe des points extrêmes.

yD K

C

K

=

( ) ( ) ( )1 2

1

2

1 2

1 2

Max 2 2 1

Sujet à 101015

, 0

yD y u y u

u

u

u u

u u

− + −

≤

≤

+ ≤

≥

( )Domaine réalisable de yD

1 10u =

2 10u =

1 2 15u u+ =

10

10( )5,10

( )10,5Points extrêmes0 10 10 5 0

, , , ,0 0 5 10 10

( )( ) ( )( ) ( )( ) ( )( ) ( )( ) ( )

0

0

0

0

0

0

Min 40

Sujet à 2 2 0 1 0

2 2 10 1 0

2 2 10 1 5

2 2 5 1 10

2 2 0 1 100

EP y y

y y y

y y y

y y y

y y y

y y y

y

+

− + − ≤

− + − ≤

− + − ≤

− + − ≤

− + − ≤

≥

( ) ( ) ( )1 2

1

2

1 2

1 2

Max 2 2 1

Sujet à 101015

, 0

yD y u y u

u

u

u u

u u

− + −

≤

≤

+ ≤

≥

[ ]T1PrenonItération 1 s 0. ,10u =

[ ]

( )( ) ( )

T1

1 0

0 0

Prenons 0,10Ainsi

Min 40

Sujet à 2 2 0 1 10 10 10

Itération 1.

0

u

EP y y

y y y y y

y

=

+

− + − ≤ ≡ ≤ +

≥

( )1

0

0

Solution optimale de 0, 10.

Alors 40 10

EP

y y

LB y y

= =

= + =

1 10u =

2 10u =

1 2 15u u+ =

10

10( )5,10

( )10,5

( ) ( ) ( )1 2

1

2

1 2

1 2

Max 2 2 1

Sujet à 101015

, 0

yD y u y u

u

u

u u

u u

− + −

≤

≤

+ ≤

≥

( ) 0Résoudre avec 0, 10yD y y= =

( ) 1 2

1

2

1 2

1 2

Max 2

Sujet à 101015

, 0

yD u u

u

u

u u

u u

+

≤

≤

+ ≤

≥

( )1 2

1 2

Solution optimale de :

10, 5.

Alors 40 2 25.

yD

u u

UB y u u

= =

= + + =

( ) ( )

1 2 0

0

Puisque 2 25 10,ajouter la contrainte suivante à la relaxation

2 2 10 1 5

u u y

y y y

+ = > =

− + − ≤

( )( ) ( )( ) ( )

2 0

0 0

0 0

Min 40

Sujet à 2 2 0 1 10

Itér

10

a

10

2 2 10 1 5 25 25

tion 2.

0

EP y y

y y y y y

y y y y y

y

+

− + − ≤ ≡ ≤ +

− + − ≤ ≡ ≤ +

≥

( )1

0

0

Solution optimale de 0, 25.

Alors 40 25

EP

y y

LB y y

= =

= + =

( )0

Puisque 25,alors 0, 25 est une solution optimale de .

UB LB

y y EP

= =

= =

( )Pour retrouver la solution , du problème original,

résoudre où 0 :y

x y

P y = ( ) 1 2 3

1 3

2 3

1 2 3

Min 10 10 15

Sujet à 2 21

, , 0

yP x x x

x x y

x x y

x x x

+ +

+ ≥ −

+ ≥ −

≥( ) 1 2 3

1 3

2 3

1 2 3

Min 10 10 15

Sujet à 21

, , 0

yP x x x

x x

x x

x x x

+ +

+ ≥

+ ≥

≥

( ) 1 2 3Solution optimale de : 1, 0, 1.yP x x x= = =

( ) 1 2 3Solution optimale de : 1, 0, 1, 0.Valeur optimale 25.

P x x x y= = = =

=

Illustration graphique

( )Domaine réalisable de EP

1y

2y

( ) ( ){ }

( )( )( )( )

0

T

0T

Min

Sujet à , 1, ,

0, 1, ,

y Y

j

j

EP f y y

F y b u y j p

F y b v j q

∈+

+ ≤ =

+ ≤ =

…

…