Méthodes de décomposition

Overview of the main decomposition

methods used

– To solve large scale problem

– To take advantage of structures

embedded in the problem
 Problem types

Min f (x) Min f (x, y)

Subject to Subject to
x ε X1 F (x, y) ≤ 0
x ε X2 x ε X, y ε Y

X1: nice constraints x : nice variables

X2: annoying constraints y : annoying variables

Column generation Constraint generation

(Dantzig – Wolfe Decomposition) (Benders Decomposition)
Lagrangean relaxation
Décomposition de Dantzig-Wolfe
( génération de colonnes )
&
Stratégie de restriction
Problèmes linéaires
 Problème

Min f ( x ) Min c T x
Sujet à Ax = b
Sujet à x ∈ X 1
x∈ X2 Ex = b
x ∈ X 1 : contraintes faciles x≥0
x ∈ X 2 : contraintes contrariantes
contraintes faciles
contraintes contrariantes
 x3 •

•x 2 • x4
Problème équivalent x • 5
x
Problème (P) Notation: x1
•
x6
•

Min c T x
Sujet à Ax = b Γ = { x : Ex = b , x ≥ 0} .
Ex = b
x≥0 L'ensemble des points extrêmes de Γ :
{ x 1 ,… , x k } .
Problème équivalent ( EP ) Sous l'hypothèse que Γ est borné
k
Min T i
∑ λi c x (i.e., Γ est un polyhèdre)
i =1
k
Sujet à ∑ λi Ax i = b  x = ∑k λ xi où
i =1  k i =1 i
k 
∑ λi = 1 x ∈ Γ ⇔  ∑ λi = 1
i =1
λi ≥ 0, i = 1,… , k λ i =1
≥ 0, i = 1,… , k
 i
 Approche de résolution

Résoudre une suite de restrictions du problème (EP) en fixant

à 0 la valeur des variables λi associées aux points extrêmes x i
qui n'ont pas encore été générés.
Notation:
G = {i : i ∈ {1,… , k } tel que x i est déjà généré} .

Dans le problème restreint,

i ∉ G ⇒ λi =0 .
Notation:
G = {i : i ∈ {1,… , k } tel que x i est déjà généré} .

Dans le problème restreint,

i ∉ G ⇒ λi =0 .

Problème équivalent ( EP ) Problème restreint ( REPG )

k k
Min ∑ λi c x
T i
Min T i
∑ λi c x
i =1 i =1
k k
Sujet à ∑ λi Ax i = b Sujet à ∑ λi Ax i = b
i =1 i =1
k k
∑ λi = 1 ∑ λi = 1
i =1 i =1
λi ≥ 0, i = 1,… , k λi ≥ 0, i ∈ G
λi = 0, i ∉ G
Problème restreint ( REPG ) Problème restreint ( REPG )
k
T i
Min T i
∑ λi c x Min ∑ i x
λ c
i =1 i∈G
k
Sujet à ∑ λi Ax i = b Sujet à ∑ λi Ax i = b
i =1 i∈G
k
∑ λi = 1 ∑ λi = 1
i =1 i∈G
λi ≥ 0, i ∈ G λi ≥ 0, i ∈ G
λi = 0, i ∉ G
Problème équivalent ( EP ) Problème restreint ( REPG )
k
T i
Min ∑ λi c x Min T i
∑ λi c x
i =1 i∈G
k
Sujet à ∑ λi Ax = b
i
Sujet à ∑ λi Ax i = b
i =1 i∈G
k
∑ λi = 1 ∑ λi = 1
i =1 i∈G
λi ≥ 0, i = 1,… , k λi ≥ 0, i ∈ G

Pour illustrer le déroulement d'une itération typique de la procédure,

supposons qu'il y a suffisemment de points extrêmes qui ont déjà
été générés pour pouvoir identifier des solutions de base du
problème restreint ( REPG ) avec ceux-ci.
(C'est-à-dire que s'il y a m contraintes contrariantes, alors G ≥ m + 1.)
Problème équivalent ( EP ) Problème restreint ( REPG )
k
T i
Min ∑ λi c x Min T i
∑ λi c x
i =1 i∈G
k
Sujet à ∑ λi Ax = b
i
Sujet à ∑ λi Axi = b
i =1 i∈G
k
∑ λi = 1 ∑ λi = 1
i =1
λi ≥ 0, i = 1,… , k i∈G
λi ≥ 0, i ∈ G

λ solution réalisable de (EP) ⇐ λ solution réalisable de (REPG )

λ solution réalisable de (EP) ⇐ λ solution optimale de (REPG )

Problème équivalent ( EP ) Problème restreint ( REPG )
k
T i
Min ∑ λi c x Min T i
∑ λi c x
i =1 i∈G
k
Sujet à ∑ λi Ax = b
i
Sujet à ∑ λi Axi = b
i =1
k i∈G
∑ λi = 1 ∑ λi = 1
i =1
λi ≥ 0, i = 1,… , k i∈G
λi ≥ 0, i ∈ G

Après avoir obtenu une solution de base optimale λ de (REPG ),

utilisons le mécanisme suivant pour
dériver des conditions assurant que λ serait aussi une solution de
base optimale pour ( EP )
et lorsqu'elles ne sont pas vérifiées, utiliser la solution de base
optimale λ pour générer une nouvelle restriction ( REPG ) .
Problème équivalent ( EP ) Problème restreint ( REPG )
k
T i
Min ∑ λi c x Min T i
∑ λi c x
i =1 i∈G
k
Sujet à ∑ λi Ax = b
i
Sujet à ∑ λi Ax i = b π
i =1
k i∈G
∑ λi = 1 ∑ λi = 1 α
i =1
λi ≥ 0, i = 1,… , k i∈G
λi ≥ 0, i ∈ G

Soient π , α les multiplicateurs du simplexe associés à la solution

optimale λ de (REPG ).
Problème équivalent ( EP ) Problème restreint ( REPG )
k
T i
Min ∑ λi c x Min T i
∑ λi c x
i =1 i∈G
k
Sujet à ∑ λi Ax = b
i
Sujet à ∑ λi Ax i = b π
i =1
k i∈G
∑ λi = 1 ∑ λi = 1 α
i =1
λi ≥ 0, i = 1,… , k i∈G
λi ≥ 0, i ∈ G

Sous l'hypothèse de non dégénérescence, puisque λ est une solution

de base optimale, alors les coûts relatifs des variables λi , i ∈ G,
sont non-négatifs:
c T xi − π T Ax i − α ≥ 0 i ∈ G.
Si les coûts relatifs des autres variables λi , i ∉ G, sont aussi
non-négatifs: Mais rappelons que
T i T
c x − π Ax − α ≥ 0
i
i ∉ G, les vecteurs xi , i ∉ G
alors λ est optimale pour (EP). ne sont pas connus
Mais tout de même, vérifier que
c T xi − π T Ax i − α ≥ 0 i ∈ {1,… , k }
est équivalent de vérifier que
Min {c T x i − π T Ax i − α } ≥ 0.
i =1,, k

De plus, puisque le minimum d'un problème de programmation

linéaire est toujours atteint en un point extrême, alors le
problème devient equivalent de vérifier que
Min {c T x − π T Ax − α } ≥ 0
x∈Γ

ou encore que la valeur optimale du problème de programmation

linéaire défini avec les contraintes faciles
( SPλ ) Min ( c T − π T A ) x − α
Sujet à Ex = b
x≥0
est non négative.
ou encore que la valeur optimale du problème de programmation
linéaire défini avec les contraintes faciles
(SPλ ) Min ( c T − π T A ) x − α
Sujet à Ex = b
x≥0
est non négative.

Si c'est le cas ( valeur optimale de ( SPλ ) est non négative ) ,

alors λ est une solution optimale de ( EP) et

x = ∑ λi xi est une solution du problème original ( P ).
i∈G
ou encore que la valeur optimale du problème de programmation
linéaire défini avec les contraintes faciles
(SPλ ) Min ( c T − π T A ) x − α
Sujet à Ex = b
x≥0
est non négative.
λ
Sinon, dénotons par x un point extrême de Γ solution
optimale de ( SPλ ) où
(c T T
) λ
− π A x − α < 0.

Alors un nouveau problème restreint est généré en introduisant

λ
une nouvelle colonne associée à x et la variable correspondante
λλ dans le problème restreint actuel.
 λ
Si par contre x est tel que
( )
c T − π T A x* − α < 0
alors un nouveau problème restreint est généré en introduisant
λ
une nouvelle colonne associée à x et la variable correspondante
λ
λ dans le problème restreint actuel.
Problème restreint

Min ∑ λi c T xi + λλ c T x λ
i∈G

Sujet à ∑ λi Axi + λλ Ax λ = b
i∈G

∑ λi + λλ = 1
i∈G
λi ≥ 0, i ∈ G
λλ ≥ 0
 Problème restreint
T λ
Min ∑ λi c x + λλ c x
T i

i∈G
λ
Sujet à ∑ λi Ax + λλ Ax = b
i

i∈G

∑ λi + λλ = 1
i∈G
λi ≥ 0, i ∈ G
Note. λλ ≥ 0
La solution λ optimale pour la restriction précédente combinée
avec λλ = 0 constitue une solution de base réalisable pour le
nouveau problème restreint.
( T T
) λ
Alors puisque le coût relatif c − π A x − α de la variable
λλ est négatif, celle-ci est candidate comme variable d'entrée
pour réduire la valeur de la fonction économique du nouveau
problème restreint.
Illustration graphique
X
 Note: La procédure s'adapte facilement au cas où les
contraintes faciles sont séparables en plusieurs blocs:
Min c1T x1 + … + c q T x q Problème séparable
Sujet à A1 x1 + … + Aq x q = b
E1 x1 = b1 {
Γ1 = x1 : E1 x1 = b 1 , x1 ≥ 0 }
 
q
Eq x = b q
{
Γ q = x q : E1 x q = b q , x q ≥ 0 }
x1 ,… , x q ≥ 0
Sous l'hypothèse que
Utilisons les points Γ r est borné
extrêmes de Γ r (i.e., Γ r est un polyhèdre)
 xr = ∑ kr

{ x r1 ,… , x rkr }  k i =1
λir x ri où
pour déterminer le  r r
x ∈ Γ r ⇔  ∑ λi = 1
r

problème équivalent λi =1

r
≥ 0, i = 1,… , kr
 i

 Note: La procédure s'adapte facilement au cas où les
contraintes faciles sont séparables en plusieurs blocs:
Min c1T x1 + … + c q T x q
Sujet à A1 x1 + … + Aq x q = b
E1 x1 = b1 {
Γ1 = x1 : E1 x1 = b 1 , x1 ≥ 0 }
 
q
Eq x = b q
{
Γ q = x q : E1 x q = b q , x q ≥ 0 }
x1 ,… , x q ≥ 0
Problème équivalent ( EP ) Sous l'hypothèse que
q kr Γ r est borné
r T ri
Min ∑ ∑ λi c x (i.e., Γ r est un polyhèdre)
r =1
q
i =1
kr  xr = ∑ kr
λir x ri où
Sujet à ∑ ∑ λir Ar x ri = b  k i =1
 r r
r =1
kr
i =1 x ∈ Γ r ⇔  ∑ λi = 1
r

∑ λi = 1, r = 1,… , q λ
r i =1
r
≥ 0, i = 1,… , kr
i =1  i

λir ≥ 0, i = 1,… , kr ; r = 1… , q 
Le principe de la méthode de résolution reste le même.

À chaque itération, un problème restreint est solutionné.

Problème équivalent ( EP )
q kr
r T ri
Min ∑ ∑ ic x
λ
r =1 i =1
q kr
Sujet à ∑ ∑ λir Ar x ri = b
r =1 i =1
kr
∑ i = 1, r = 1,… , q
λ r

i =1
λir ≥ 0, i = 1,… , kr ; r = 1… , q
Problème restreint ( REPG )
q kr
Min r T ri
∑ ∑ ic x
λ
r =1 i =1
q kr
Sujet à ∑ ∑ λir Ar x ri = b
r =1 i =1
kr
∑ λi = 1, r = 1,… , q
r

i =1
λir ≥ 0, i ∈ Gr r = 1… , q
λir = 0, i ∉ Gr r = 1… , q
Problème équivalent ( EP )
q kr
r T ri
Min ∑ ∑ ic x
λ
r =1 i =1
q kr
Sujet à ∑ ∑ λir Ar x ri = b
r =1 i =1
kr
∑ λi = 1, r = 1,… , q
r

i =1
λir ≥ 0, i = 1,… , kr ; r = 1… , q

Problème restreint ( REPG )

q kr
r T ri
Min ∑ ∑ λi c x
r =1 i =1
q kr
Sujet à ∑ ∑ λir Ar x ri = b
r =1 i =1
kr
∑ λi = 1, r = 1,… , q
r

i =1
λir ≥ 0, i ∈ Gr r = 1… , q
 Problème restreint ( REPG )
q kr
r T ri
Min ∑ ∑ ic x
λ
r =1 i =1
q kr
Sujet à ∑ ∑ λir Ar x ri = b π
r =1 i =1
kr
∑ i = 1, r = 1,… , q
λ α r
r

i =1
λir ≥ 0, i ∈ Gr r = 1… , q

Soient π , α r , r = 1,… , q, les multiplicateurs du simplexe

associés à la solution optimale λ de (REPG ).
Pour vérifier si cette solution est optimale pour le
problème équivalent, q sous-problèmes (SPλr ), r = 1,… , q
sont résolus.
( SPλr ) Min ( c T − π T A ) x r − α r
Sujet à Er x r = b r
xr ≥ 0
Si la valeur optimale de tous les sous-problèmes est supérieure
ou égale à 0, alors la solution est optimale pour le problème
équivalent.

Sinon, pour les blocs r où la valeur optimale est négative, une

r λ
nouvelle variable λλ associée au point extrême x (solution
r

optimale) est introduite pour définir un nouveau problème

restreint.
 Interprétation économique
Supposons que le problème est utilisé pour modeliser les
opérations d'une firme ayant q succursales où la production
est complétée.
Min c1T x1 + … + c q T x q
1
Sujet à A1 x + … + Aq x = b
q

E1 x1
=b 1
{
Γ1 = x1 : E1 x1 = b 1 , x1 ≥ 0 }
 
Eq x q = b q {
Γ q = x q : E1 x q = b q , x q ≥ 0 }
x1 ,… , x q ≥ 0
Les contraintes contrariantes
A1 x1 + … + Aq x q = b
correspondent aux contraintes relatives aux ressources et aux
produits de l'ensemble de la firme.
Γ r correspond aux contraintes d'opérations de la succursale r
 Les contraintes contrariantes
A1 x1 + … + Aq x q = b
correspondent aux contraintes relatives aux ressources et aux
produits de l'ensemble de l'entreprise.
Γ r correspond aux contraintes d'opérations de la succursale r
{
Les points extrêmes de Γ r , x r1 ,… , x rkr } représentent des modes
d'opérations de la succursale r.
Interprétation de problème restreint:
Étant donnés des sous-ensembles de modes d'opérations des r succursales,
la firme optimise la planification de sa production globale. De plus,
à la lumière de sa planification, elle spécifie des prix π pour les
ressources et les produits.
Problème restreint ( REPG )
q kr
Min r T ri
∑ ∑ λi c x
r =1 i =1
q kr
Sujet à ∑ ∑ λir Ar x ri = b π
r =1 i =1
kr
∑ λi = 1, r = 1,… , q
r

i =1
αr
λi ≥ 0, i ∈ Gr r = 1… , q
r
 Γ r correspond aux contraintes d'opérations de la succursale r

{
Les points extrêmes de Γ r , x r1 ,… , x rkr } représentent des modes
d'opérations de la succursale r.
Interprétation de problème restreint:
Étant donnés des sous-ensembles de modes d'opérations des r succursales,
la firme optimise la planification de sa production globale. De plus,
à la lumière de sa planification, elle spécifie des prix π pour les
ressources et les produits.

( )
Interprétation des sous-problèmes SPλr :
La firme transmet les prix π aux succursales. Elle leur demande
de réoptimiser leurs opérations à la lumière de ces derniers afin
de fournir de nouveaux modes d'opérations.
( SPλr ) Min ( c T − π T A ) x r − α r
Sujet à Er x r = b r
xr ≥ 0
 Initialisation de la procédure

Pour générer les ( m + 1) points extrêmes de Γ nécessaires pour

définir le premier problème restreint, nour utilisons une phase
préliminaire très similaire à la phase I du simplexe.
Déterminons un premier point extrême x1 de Γ en appliquant une
phase I du simplexe au problème défini avec les contraintes faciles
Min c T x
Sujet à Ex = b
x ≥ 0.
Déterminons un premier point extrême x1 de Γ en appliquant une
phase I du simplexe au problème défini avec les contraintes faciles
Min c T x
Sujet à Ex = b
x ≥ 0.
Considérons le problème équivalent auxiliaire ( EPA) suivant
k
Min ∑ λi 0 + τ1 + … + τ j + … + τ m
i =1
k
Sujet à ∑ i
λ Ax i
± τ 1e1
± … ± τ j e j
± … ± τ m e m
=b
i =1
k
∑ λi =1
i =1
λi ≥ 0, i = 1,… , k
τ j ≥ 0, j = 1,… , m
T
où e ∈ R est le vecteur unitaire [ 0,… ,1,… ,0] avec le 1
j m

en j ième position.
Le signe devant chaque variable τ j est choisi de telle sorte que
τ j ≥ 0 et qu'il y ait une solution trivial au problème restreint
suivant associé à ( EPA)
k
Min ∑ λi 0 + τ1 + … + τ j + … + τ m
i =1
k
Sujet à ∑ i
λ Ax i
± τ 1e1
± … ± τ j e j
± … ± τ m e m
=b
i =1
k
∑ λi =1
i =1
λ1 ≥ 0
λi = 0, i = 2,… , k
τ j ≥ 0, j = 1,… , m.
Le signe devant chaque variable τ j est choisi de telle sorte que
τ j ≥ 0 et qu'il y ait une solution trivial au problème restreint
suivant associé à ( EPA)

k
Min ∑ λi 0 + τ1 + … + τ j + … + τ m
i =1
k
Sujet à ∑ i
λ Ax i
± τ 1e1
± … ± τ j e j
± … ± τ m e m
=b
i =1
λ1 =1
λ1 ≥ 0
λi = 0, i = 2,… , k
τ j ≥ 0, j = 1,… , m.
 k
Min ∑ λi 0 + τ1 + … + τ j + … + τ m
i =1
k
Sujet à ∑ i
λ Ax i
± τ 1e1
± … ± τ j e j
± … ± τ m e m
=b
i =1
λ1 =1
λ1 ≥ 0
λi = 0, i = 2,… , k
τ j ≥ 0, j = 1,… , m.

Puisque λ1 = 1, alors les m premières Ainsi pour chaque j = 1,… , m,

contraintes se reduisent à
1 1 j m
( )
Ax1 ± τ j = b j
j
Ax ± τ1e ± … ± τ j e ± …τ m e = b.
ou encore
± τ j = b j − Ax1 .( ) j
 k
Min ∑ λi 0 + τ1 + … + τ j + … + τ m
i =1
k
Sujet à ∑ i
λ Ax i
± τ 1e1
± … ± τ j e j
± … ± τ m e m
=b
i =1
λ1 =1
λ1 ≥ 0
λi = 0, i = 2,… , k
τ j ≥ 0, j = 1,… , m.

Donc pour chaque j = 1,… , m, Ainsi pour chaque j = 1,… , m,

tel que
( )
Ax1 ± τ j = b j
( )
b j − Ax1 ≥ 0
j ou encore
j

alors le signe devant τ j est +

pour avoir τ j ≥ 0.
( )
± τ j = b j − Ax1
j
.
 k
Min ∑ λi 0 + τ1 + … + τ j + … + τ m
i =1
k
Sujet à ∑ i
λ Ax i
± τ 1e1
± … ± τ j e j
± … ± τ m e m
=b
i =1
λ1 =1
λ1 ≥ 0
λi = 0, i = 2,… , k
τ j ≥ 0, j = 1,… , m.

Donc pour chaque j = 1,… , m, Ainsi pour chaque j = 1,… , m,

tel que
( )
Ax1 ± τ j = b j
( )
b j − Ax1 < 0
j ou encore
j

alors le signe devant τ j est −

pour avoir τ j ≥ 0.
( )
± τ j = b j − Ax1
j
.
Nous appliquons la décomposition de Dantzig-Wolfe au
problème auxiliaire équivalent ( EPA) pour reduire la valeur
 m 
de la somme des variables artificielles  ∑τ j  .
 j =1 
 
Au cours de cette résolution, nous générons des points extrêmes
de Γ.
 m 
Si la valeur de  ∑τ j  est réduite à 0, alors sous l'hypothèse de
 j =1 
 
non dégénérescence, au moins ( m + 1) points extrêmes de Γ sont
générés.
Avec ces ( m + 1) points extrêmes de Γ, nous retournons à la
résolution de (EP).
 m 
Si  ∑τ j  > 0 à l'optimum, alors le problème ( EP ) n'est pas
 j =1 
 
réalisable.
Note. Puisque les coefficients des variables λi dans la fonction
économique de ( EPA ) sont 0
k
Min ∑ λi 0 + τ1 + … + τ j + … + τ m
i =1
k
Sujet à ∑ i
λ Ax i
± τ 1e1
± … ± τ j e j
± … ± τ m e m
=b π
i =1
k
∑ λi =1 α
i =1
λi ≥ 0, i = 1,… , k
τ j ≥ 0, j = 1,… , m

alors les sous problèmes pour vérifier si la solution optimale du

problème restreint est optimal pour le problème equivalent
auxiliaire sont de la forme suivante
(
Min 0T − π T A x − α )
Sujet à Ex = b
x ≥ 0.
étant donné la solution optimale λ,τ pour le probleme restreint de ( EPA )

Min ∑ λi 0 + τ1 + … + τ j + … + τ m
i∈G

Sujet à ∑ i
λ Ax i
± τ 1e1
± … ± τ j e j
± … ± τ m e m
=b π
i∈G

∑ λi =1 α
i∈G
λi ≥ 0, i ∈G
τ j ≥ 0, j = 1,… , m
Coût relatif de λi :
0 − π T Axi − α
alors le sous problème pour vérifier si la solution optimale λ,τ du
problème restreint est optimal pour le problème equivalent
auxiliaire ( EPA ) est de la forme suivante
Min 0 − π T Ax − α
Sujet à Ex = b
x ≥ 0.
 Existence de bornes inférieure et supérieure
sur la valeur optimal
À chaque résolution d'un problème restreint, la solution optimale
λ est réalisable pour le problème équivalent ( EP). Donc sa valeur
∑
z = λ c T xi est une borne supérieur sur la valeur optimale z de ( EP) :
i
i∈G
z ≤ z = ∑ λi c T xi .
i∈G

De plus, par le théorème Problème restreint ( REPG )

de dualité forte T i
Min ∑ λi c x
z = ∑ λi c T xi = π T b + α . i∈G

i∈G Sujet à ∑ λi Ax i = b π
i∈G

∑ λi = 1 α
i∈G
λi ≥ 0, i ∈ G
Pour dériver une borne inférieure sur z , considérons une
combinaison linéaire des contraintes de ( EP ) en utilisant les
multiplicateurs optimaux du simplexe π et α de ( REPG ) :
k
Min z = ∑ λi c T xi
i =1
k
Sujet à ∑ i =b
λ Ax i
π
i =1
k
∑ λi = 1 α
i =1
λi ≥ 0, i = 1,… , k
pour obtenir
k
− ∑ i
λ π
i =1
 T
Ax( )
i + α = π T b + α

Soustrayons cette équation de la fonction économique:

k
∑ i
λ
i =1
c (
T i
x − π T
Ax ) (
i − α = z − π T b + α .
)
Soustrayons cette équation de la fonction économique:
k
∑ i
λ c
i =1
x(
T i
− π T
Ax ) (
i − α = z − π T b + α .
)

De plus, par le théorème Problème restreint ( REPG )

de dualité forte T i
Min ∑ λi c x
z = ∑ λi c T xi = π T b + α . i∈G

i∈G Sujet à ∑ λi Ax i = b π
i∈G

∑ λi = 1 α
i∈G
λi ≥ 0, i ∈ G
Soustrayons cette équation de la fonction économique:
k
∑ i
λ c T i
x
i =1
− π(T
Ax )
i − α = z − π T b + α .
( )
par le théorème de dualité forte
z = ∑ λi c T xi = π T b + α .
i∈G
Ainsi
k (SPλ ) Min ( c T − π T A ) x − α
∑ i
λ
i =1
c T i
x − π(
 T
Ax i − α = z − z. ) Sujet à Ex = b
x≥0

λ
Puisque x est une solution optimale du sous problème ( SPλ )
( T λ T λ
) (
c x − π Ax − α ≤ c T xi − π T Ax i − α ) i = 1,… , k .

Par conséquent, puisque λi ≥ 0, i =1,… ,k

k k
∑ i
λ
i =1
c x − π(
 T
AxT λ
− 
α ≤ ∑ i
λ c T i
x − πλ
T
)
Ax i − α = z − z.
i =1
( )
 Par conséquent, puisque λi ≥ 0, i =1,… ,k
k k
∑ i
λ
i =1
c x (
− πT λ
T
Ax − 
α ≤ ∑ i
λ c λ
T i
x −)π T

i =1
( )
Ax i − α = z − z.

k
Mais également ∑ λi = 1
i =1
et alors
(c xT λ T λ
)
− π Ax − α ≤ z − z
ou encore
(c xT λ T λ
)
− π Ax − α + z ≤ z

borne inférieure
 En somme
( T λ 
)
c x − π T Ax λ − α + z ≤ z ≤ z

valeur optimale valeur optimale du

de ( SPλ ) problème équivalent restreint

pas nécessairement non décroissante non croissante d'une

d'une itération à l'autre itération à l'autre
Néanmoins, dénotons par LB la plus grande borne inférieure
générée jusqu'ici au cours de la résolution. Cette valeur est mise
à jour à chaque résolution d'un nouveau problème restreint.

Si z − LB ≤ ε ,
alors puisque LB ≤ z ≤ z,
il s'ensuit que z − z ≤ z − LB ≤ ε
et la solution actuelle λ est ε -optimale.
 Convergence de la procédure de Dantzig-Wolfe

Considérons le problème équivalent ( EP ) et démontrons la

convergence de la procédure de Dantzig-Wolfe une fois que
la phase préliminaire a été complétée pour générer (m + 1)
points extrême de Γ. Notons que la même preuve s'applique
pour démontrer la convergence de la phase préliminaire.

Formulons la procédure de Dantzig-Wolfe dans le cadre de la

stratégie de restriction.
Initialisation. Soit z = ∞. Soit G ⊂ {1,… , k }. Rappelons que nous
dénotons le problème restreint du problème équivalent ( EP)
associé au sous-ensemble G par ( REPG ).
Étape 1. Résoudre le problème (REPG ).
Si (REPG ) n'est pas borné inférieurement, alors la procédure
s'arrête car le problème équivalent est également non borné
inférieurement. (Ceci ne s'applique que lorsque Γ n'est pas borné.)
Autrement, soient z la valeur optimale et λ une solution optimale
de ( REPG ), et soient π , α les multiplicateurs optimaux correspondants.

Étape 2. Vérifier si λ est aussi une solution optimale de ( EP)

en vérifiant si les coûts relatifs des variables λi associés aux points
extrêmes xi , i ∉ G, sont aussi non négatifs: Problème restreint ( REP ) G
T i
T T Min ∑ λi c x
c x − π Ax − α ≥ 0
i i
i ∉ G, i∈G

Sujet à ∑ λi Ax i = b π
i∈G

∑ λi = 1 α
i∈G
λi ≥ 0, i ∈ G
Étape 1. Résoudre le problème (REPG ).
Si (REPG ) n'est pas borné inférieurement, alors la procédure
s'arrête car le problème équivalent est également non borné
inférieurement. (Ceci ne s'applique que lorsque Γ n'est pas borné.)
Autrement, soient z la valeur optimale et λ une solution optimale
de ( REPG ), et soient π , α les multiplicateurs optimaux correspondants.

Étape 2. Vérifier si λ est aussi une solution optimale de ( EP)

en vérifiant si les coûts relatifs des variables λi associés aux points
extrêmes xi , i ∉ G, sont aussi non négatifs:
c T x i − π T Ax i − α ≥ 0 i ∉ G,
Pour y arriver, résoudre le sous-problème (SPλ ). Si la valeur
optimale est non négative, alors λ est aussi solution optimale
de ( EP), et la procédure s'arrête.
( SPλ ) Min ( c − π A) x − α
T T

Sujet à Ex = b
x≥0
Étape 2. Vérifier si λ est aussi une solution optimale de ( EP)
en vérifiant si les coûts relatifs des variables λi associés aux points
extrêmes xi , i ∉ G, sont aussi non négatifs.
Pour y arriver, résoudre le sous problème (SPλ ). Si la valeur
optimale est non négative, alors λ est aussi solution optimale
de ( EP), et la procédure s'arrête.
λ
Étape 3. Sinon, dénotons par x la solution optimale de ( SPλ ).
λ
x est un point extrême de Γ dont l'indice n'appartient pas à G.
Incluons son indice dans un ensemble V . Dans la présentation précédente,
{ }
Définissons l'ensemble D ⊂ i ∈ G : λi = 0 . nous supposions que D = Φ
Étape 4. Si z < z , alors z = z, remplacer G par G′ = G ∪ V − D et
reprendre l'étape 1.
Si z = z , alors remplacer G par G′ = G ∪ V et reprendre l'étape 1.
( SPλ ) Min ( c T − π T A) x − α
Sujet à Ex = b
x≥0
Lemme 1. La solution optimale λ de ( REPG ) est aussi optimale
pour le problème restreint ( REPG - D ). D ⊂ {i ∈ G : λi = 0} .

Preuve. Puisque les contraintes du problème ( REPG - D ) sont

plus restrictives que celles de ( REPG ) (en effet il y a plus de
variables forcées de prendre la valeur 0 dans ( REPG - D )), alors
val. opt ( REPG - D ) ≥ val. opt ( REPG ) = z.
{ }
Mais par définition de D ⊂ i ∈ G : λi = 0 , il s'ensuit que λ est
une solution réalisable de ( REPG - D ), et ainsi
z ≥ val. opt ( REPG - D ).
Par conséquent z = val. opt ( REPG - D ) et λ est aussi optimale
pour le problème restreint ( REPG - D ). 
Lemme 2. val. opt ( REPG′ ) ≤ val. opt ( REPG ).

Preuve. Si G′ = G ∪ V , alors le domaine réalisable de ( REPG′ ) est

plus grand que celui de ( REPG ) et
val. opt ( REPG′ ) ≤ val. opt ( REPG ).

Si G′ = G ∪ V − D, alors par le lemme 1,

val. opt ( REPG − D ) = val. opt ( REPG ).
Ainsi le résultat est vérifié avec l'argument plus haut. 
Théorème 3. La procédure de Dantzig-Wolfe se termine en un
nombre fini d'itérations.

Preuve. Puisque l'ensemble des indices des points extrêmes

{1,… ,k } est fini, alors il comporte un nombre fini de sous-ensembles
différents.

Aussi longtemps que les valeurs optimales des problèmes restreints

diminuent strictement d'une itération à l'autre, alors le même
sous-ensemble de {1,… ,k } ne peut se répéter pour définir un
problème restreint.

De plus, lorsque la valeur optimale n'est pas améliorée, un nouvel

indice est ajouté au sous-ensemble utilisé pour définir le prochain
problème restreint. Ainsi, la valeur optimale ne peut rester constante
que pour un nombre fini de fois avant que le sous-ensemble utilisé
pour définir le prochain problème restreint ne soit égal à {1,… ,k }.

Notes.
Le même argument s'applique pour démontrer la convergence
au cours de la phase péliminaire.
Globalement, la procédure de Dantzig-Wolfe converge en un
nombre fini d'itérations car les problèmes restreints et les
sous problèmes peuvent être résolus avec le simplexe qui
converge en un nombre fini d'itérations.
 Exemple numérique
Considérons l'exemple suivant tiré du livre de Lasdon (p. 155)

Min z = − x1 − x2 − 2 y1 − y2
Sujet à x1 + 2 x2 + 2 y1 + y2 ≤ 40
x1 + 3x2 ≤ 30
Γ1 2 x + x ≤ 20
1 2
y1 ≤ 10 Γ = Γ1 ∪ Γ 2
Γ2 y2 ≤ 10
y1 + y2 ≤ 15
x1 , x2 , y1 , y2 ≥ 0
 x1 + 3 x2 ≤ 30 y2 y1 ≤ 10
x2
2 x1 + x2 ≤ 20 y2 ≤ 10
y1 + y2 ≤ 15
x1 , x2 ≥ 0 15
y1 , y2 ≥ 0
( 5,10 )
20 10

10 ( 6,8) 5 (10,5)

x1 5 10 15 y1
10 20 30

Le premier problème équivalent

Min z = − x1 − x2 − 2 y1 − y2 restreint est obtenu en utilisant
T
Sujet à x1 + 2 x2 + 2 y1 + y2 ≤ 40 x1 = y1 = [ 0, 0]
x1 + 3 x2 ≤ 30
2 x1 + x2 ≤ 20
Min z = 0λ1 + 0 µ1
y1 ≤ 10 Sujet à 0λ1 + 0 µ1 +s = 40
y2 ≤ 10 λ1 =1
y1 + y2 ≤ 15 µ1 = 1
x1 , x2 , y1 , y2 ≥ 0 λ1 ,µ1 ,s ≥ 0
 Min z = 0λ1 + 0µ1
Sujet à 0λ1 + 0 µ1 +s = 40 π
λ1 =1 α
µ1 = 1 γ
λ1 ,µ1 ,s ≥ 0
La solution optimale de ce problème est λ1 = µ1 = 1, s = 40,
les multiplicateurs sont π =α =γ =0, et la valeur optimale est z = 0.
 x1 + 3 x2 ≤ 30 y2 y1 ≤ 10
x2
2 x1 + x2 ≤ 20 y2 ≤ 10
y1 + y2 ≤ 15
x1 , x2 ≥ 0 15
y1 , y2 ≥ 0
( 5,10 )
20 10
*T
x = [ 6,8] *T
10 ( 6,8) 5 (10,5) y = [10,5]
v. opt = −14
v. opt = −25
x1 5 10 15 y1
10 20 30

c = [ −1, −1]
T Sous-problèmes à résoudre c T = [ −2, −1]
Min ( c T − π T A ) x − α A = [ 2,1]
A = [1, 2]
π = 0, α = 0 Sujet à Ex = b π = 0, γ = 0
x≥0
Min − x1 − x2 Min − 2 y1 − y2
Sujet à x1 + 3x2 ≤ 30 Sujet à y1 ≤ 10
2 x1 + x2 ≤ 20 y2 ≤ 10
x1 , x2 ≥ 0 y1 + y2 ≤ 15
y1 , y2 ≥ 0
LB = 0 − 14 − 25 = −39
 Puisque − 39 = LB < z = 0, nous poursuivons.
Min z = − x1 − x2 − 2 y1 − y2
Le prochain problème équivalent Sujet à x1 + 2 x2 + 2 y1 + y2 ≤ 40
restreint est obtenu en ajoutant λ2 x1 + 3 x2 ≤ 30
et µ2 associés respectivement à 2 x1 + x2 ≤ 20
T T y1 ≤ 10
2 2
x = [ 6,8] et y = [10,5] y2 ≤ 10
Problème restreint y1 + y2 ≤ 15

Min ∑ λi c T xi + λλ c T x λ
i∈G
x1 , x2 , y1 , y2 ≥ 0

Sujet à ∑ λi Ax i + λλ Ax λ = b
i∈G

∑ λi + λλ = 1 7 15
i∈G
λi ≥ 0, i ∈ G λ1 = , λ2 =
λλ ≥ 0 22 22
µ1 = 0, µ 2 = 1
Min z = 0λ1 − 14λ2 + 0 µ1 − 25µ2 6
0λ1 + 22λ2 + 0µ1 +25µ2 +s = 40 z = −34 11

Sujet à
λ1 +λ2 =1 14 200
π = − , α = 0, γ = −
µ1 + µ2 = 1 22 22
λ1 ,λ2 , µ1 ,µ2 , s ≥ 0
 x1 + 3 x2 ≤ 30 y2 y1 ≤ 10
x2
2 x1 + x2 ≤ 20 y2 ≤ 10
y1 + y2 ≤ 15
x1 , x2 ≥ 0 15
y1 , y2 ≥ 0
( 5,10 )
*T
20
x = [10, 0] 10

*T
10 ( 6,8) 80 5 (10,5) y = [10,5]
v. opt = −
22 v. opt = 0
c T = [ −1, −110] 20 30 c10T =15[ −2, −1] 1
x1 5 y

A = [1, 2] Sous-problèmes
6 T 80 T à résoudre 2 A = [ 2,1]
14 34 ( c− − π −A0)=x −38
LB = −Min α 14 200
π = − , α = 0 11 22 11 π = − , γ = −
22 Sujet à Ex = b 22 22
8 6 x≥0
Min − x1 + x2 16 8 200
Min − y1 − y2 +
22 22 22 22 22
Sujet à x1 + 3 x2 ≤ 30 Sujet à y1 ≤ 10
2 x1 + x2 ≤ 20 y2 ≤ 10
x1 , x2 ≥ 0 y1 + y2 ≤ 15
y1 , y2 ≥ 0
 2 6
Puisque − 38 = LB < z = −34 , nous poursuivons.
11 11
Min z = − x1 − x2 − 2 y1 − y2
Sujet à x1 + 2 x2 + 2 y1 + y2 ≤ 40
Le prochain problème équivalent
x1 + 3 x2 ≤ 30
restreint est obtenu en ajoutant λ3 2 x1 + x2 ≤ 20
3 T
associé à x = [10, 0] y1 ≤ 10
y2 ≤ 10
y1 + y2 ≤ 15
x1 , x2 , y1 , y2 ≥ 0
Min z = 0λ1 − 14λ2 − 10λ3 + 0 µ1 − 25µ2
Problème restreint
Sujet à 0λ1 + 22λ2 + 10λ3 + 0 µ1 +25µ2 +s = 40 Min ∑ λ c x + λ c x
i∈G
i
T i
λ
T λ

λ1 +λ2 +λ3 =1 Sujet à ∑ λ Ax + λ Ax = b

i∈G
i
i
λ
λ

µ1 + µ2 = 1 ∑ λ + λ =1
i∈G
λ ≥ 0, i ∈ G
i λ

λ1 ,λ2 , λ3 , µ1 ,µ2 , s ≥ 0
i
λ ≥0 λ

5 7 2
λ1 = 0, λ2 = , λ3 = , µ1 = 0, µ 2 = 1, z = −36
12 12 3
4 80 200
π = − , α = − , γ = −
 
12 12 12
 x1 + 3 x2 ≤ 30 y2 y1 ≤ 10
x2
2 x1 + x2 ≤ 20 y2 ≤ 10
y1 + y2 ≤ 15
x1 , x2 ≥ 0 15
y1 , y2 ≥ 0
( 5,10 )
20 10
*T
x = [10, 0] ou [ 6,8] *T
10 ( 6,8) 5 (10,5) y = [10,5]
v. opt = 0
v. opt = 0
c T = [ −1, −1] 10 c10T =15[ −2, −1] 1
x1 5 y
20 30

A = [1, 2] Sous-problèmes
2T à résoudre2 A = [ 2,1]
4 −36( c −−0π−T 0A )=x−−36
80 LB =Min α 4 200
π = − , α = − 3 3 π = − , γ = −
12 12 Sujet à Ex = b 12 12
2 1 80 x≥0
Min − x1 − x2 + 4 2 200
Min − y1 − y2 +
3 3 12 3 3 12
Sujet à x1 + 3x2 ≤ 30 Sujet à y1 ≤ 10
2 x1 + x2 ≤ 20 y2 ≤ 10
x1 , x2 ≥ 0 y1 + y2 ≤ 15
y1 , y2 ≥ 0
Critère d'optimalité satisfait puisque les deux sous-problèmes
ont une valeur optimale égale à 0.
5 7 2 T
x1 = [ 0, 0]
T
y1 = [ 0, 0]
λ1 = 0, λ2 = , λ3 = , µ1 = 0, µ 2 = 1, z = −36 T T
12 12 3 x 2 = [6,8] y 2 = [10,5]
T
x3 = [10, 0]

Donc une solution optimale du problème original est

 25 
5 6  7 10   3 
x= + = 
 8   0 
12   12   10 
3 
y = 10 
5 

2
valeur optimale= − 36 .
3
 Cas où Г n’est pas borné
Problème (P) Notation:
Min c T x
Sujet à Ax = b Γ = { x : Ex = b , x ≥ 0} .
Ex = b
x≥0 L'ensemble des points extrêmes de Γ :
{ x 1 ,… , x k } .
Si l'hypothèse que Γ est borné n'est pas vérifiée
(i.e., Γ est un polytope), alors il n'est plus vrai que
 x = ∑k λ xi où
 k i =1 i

x ∈ Γ ⇔  ∑ λi = 1
 λ ≥ 0, i = 1,… , k
i =1

 i
 X = {( x, y ) : − x + y ≤ 1; − x + 2 y ≤ 3; − x ≤ 0; − y ≤ 0}
−x + y = 1

−x + 2 y = 3 Points extrêmes de X :
( 0, 0 ) , ( 0,1) , (1, 2 )
(1, •2 ) K enveloppe convexe
des points extrêmes
•
( 0,1)•
•
( 0, 0 )
Nous devons avoir recours au théorème de résolution de Goldman
pour dériver un problème équivalent.
Théorème de résolution de Goldman:
Pour tout polytope X = { x ∈ R n : Ax ≤ b} ≠ Φ, il existe un
polyèdre K et un cône C tels que
X = K + C.
De plus, si la matrice A est de plein rang, il existe une résolution
où K est l'enveloppe convexe des points extrêmes de X et où
C = { x ∈ R n : Ax ≤ 0} .
Conséquence:
si {u1 ,… , u g } dénote l'ensemble des points extrêmes de X
si {v1 ,… , v h } dénote l'ensemble des générateurs du cône C ,
alors
{ g
K = x ∈ R : x = ∑ θi ui ;
n

i =1
g
∑ θi = 1; θi ≥ 0, i = 1,… , g
i =1
}
C = {x ∈ R : x = ∑ ϕ v ; }
h
n
i i
ϕi ≥ 0, i = 1,… , h
i =1

Si x ∈ X = K + C , alors x est de la forme

g h
x = ∑ θi ui + ∑ ϕi vi
i =1 i =1
g
où ∑ θi = 1; θi ≥ 0, i = 1,… , g ; ϕi ≥ 0, i = 1,… , h
i =1
 X = {( x, y ) : − x + y ≤ 1; − x + 2 y ≤ 3; − x ≤ 0; − y ≤ 0}

Points extrêmes de X :
( 0, 0 ) , ( 0,1) , (1, 2 )
(1,•2 ) K enveloppe convexe
des points extrêmes
( 0,1)• ( 2,1)
•

• • Points générateurs du cône C:

( 0, 0 ) (1, 0 ) (1,0 ) et ( 2,1)
satisfaisant le système suivant:
−x + y ≤ 0
−x + 2 y ≤ 0
−x ≤ 0
−y ≤ 0
 X = {( x, y ) : − x + y ≤ 1; − x + 2 y ≤ 3; − x ≤ 0; − y ≤ 0}

Points extrêmes de X :
( 0, 0 ) , ( 0,1) , (1, 2 )
(1, •2 ) K enveloppe convexe
des points extrêmes
( 0,1)• ( 2,1)
•

• • Points générateurs du cône C:

( 0, 0 ) ( 0,1) ( 0,1) et ( 2,1)
satisfaisant le système suivant:
−x + y ≤ 0
−x + 2 y ≤ 0
−x ≤ 0
−y ≤ 0
Appliquons le théorème de résolution de Goldman au polytope
Γ = { x : Ex = b , x ≥ 0} .
Dénotons
{ }
u1 ,… , u g , l'ensemble des points extrêmes de Γ
{v ,…, v } , l'ensemble des générateurs du cône C,
1 h

alors
 g g 
K =  x ∈ R : x = ∑ θi ui ; ∑ θi = 1; θi ≥ 0, i = 1,… , g 
n

 i =1 i =1 
 h 
C =  x ∈ R : x = ∑ ϕi vi ; ϕi ≥ 0, i = 1,… , h 
n

 i =1 

Si x ∈ Γ = K + C , alors x est de la forme

g h
x = ∑ θi ui + ∑ ϕi vi
i =1 i =1
g
où ∑θi = 1; θi ≥ 0, i = 1,… , g ; ϕi ≥ 0, i = 1,… , h .
i =1
 Problème équivalent

Problème (P)
Min c T x
Sujet à Ax = b Si x ∈ Γ = K + C , alors
g
Ex = b h
x≥0 x = ∑ θi ui + ∑ ϕi vi
i =1 i =1
g
Problème équivalent ( EP ) où ∑ θi = 1; θi ≥ 0,
g h
T T i i =1
Min ∑ θ i c u + ∑ ϕi c v
i

i =1
g
i =1
h
θi ≥ 0, i = 1,… , g
Sujet à ∑ θi Au i + ∑ ϕi Av i = b ϕi ≥ 0, i = 1,… , h .
i =1 i =1
g
∑ θi = 1
i =1
θi ≥ 0, i = 1,… , g
ϕi ≥ 0, i = 1,… , h
Le choix du type de variables à introduire pour générer le prochain
problème restreint depend de l'issue de la résolution du sous-problème
( SP ) défini avec les contraintes faciles.

θϕ

( SPθϕ  ) Min ( c T − π T A ) x − α
Sujet à Ex = b
x≥0


Si le minimum est atteint au point extrême uθϕ et si
(
T T θϕ
)

c − π A u − α < 0
alors un nouveau problème restreint est généré en introduisant

θϕ
une nouvelle colonne associée à u et la variable correspondante
  dans le problème restreint actuel.
θθϕ
Le choix du type de variables à introduire pour générer le prochain
problème restreint depend de l'issue de la résolution du sous-problème
( SP ) défini avec les contraintes faciles.

θϕ

( SPθϕ  ) Min ( c T − π T A ) x − α
Sujet à Ex = b
x≥0

Si sous-problème SPθϕ( )
  n'est pas borné inférieurement, alors

θϕ
nous déterminons un point v du cône C tel
(
T T 
θϕ
)
c − π A v − α < 0
pour déterminer un nouveau problème restreint généré en

θϕ
introduisant une nouvelle colonne associée à v et la variable
correspondante ϕθϕ  dans le problème restreint actuel.
 Min c T x Itération où xs est variable d'entrée : cs < 0
Sujet à Ax = b
x≥0 Problème non borné: a• s ≤ 0

 xB   b 
x =  xs  = 0 
 xR − s  0 

c T x = cBT xB = z
 Min c T x Itération où xs est variable d'entrée : cs < 0
Sujet à Ax = b
x≥0 Problème non borné: a• s ≤ 0

 xB  b  Soit x obtenu à partir de x en augmentant xs de 1:

x =  xs  = 0   xB − a• s xs  b − a• s 
 xR − s  0  x =  xs  = 1  ≥ 0 ; c T x = cBT xB + cs
0  0 
 
c T x = cBT xB = z
 Min c T x Itération où xs est variable d'entrée : cs < 0
Sujet à Ax = b
x≥0 Problème non borné: a• s ≤ 0
Soit x obtenu à partir de x en augmentant xs de 1:
 xB   b 
x =  xs  = 0   xB − a• s xs  b − a• s 
 xR − s  0  x =  xs  = 1  ≥ 0 ; c T x = cBT xB + cs
0  0 

c T x = cBT xB = z

Soit
b − a• s  b   −a• s 
xˆ = x − x = 1  − 0  = 1  ≥ 0
0  0  0 
   

Ax = b }
Ax = b ⇒ Axˆ = A x − x = 0
( )
c T xˆ = c T ( x − x ) = cBT xB + cs − cBT xB = cs < 0
 Extension au cas non-linéaire
Soit le problème de programmation mathématique
(P) Min f ( x ) Min c T x
Sujet à Ax = b
Sujet à hi ( x ) ≤ bi i = 1,… , m
Ex = b
n
x∈Γ ⊂ R x≥0
où Γ est un ensemble convexe borné et f , hi , i = 1,… m, sont des
fonctions convexes sur Γ.

Par analogie avec le cas linéaire, considérons un ensemble de

{ }
points x1 ,… , x k de Γ afin d'approximer Γ avec l'enveloppe
convexe de ces points.
Soit le problème de programmation mathématique
Min f ( x )
Sujet à hi ( x ) ≤ bi i = 1,… , m
x ∈ Γ ⊂ Rn
où Γ est un ensemble convexe borné et f , hi , i = 1,… m, sont des
fonctions convexes sur Γ.
Par analogie avec le cas linéaire, considérons un ensemble de
{ }
points x1 ,… , x k de Γafin d'approximer Γ avec l'enveloppe
 k k 
convexe de ces points  x ∈ R : x = ∑ α j x ; ∑ α j = 1; α j ≥ 0, j = 1,… , k 
n j

 j =1 j =1 
Γ x1
5 x2
x

x 4 x3
Soit le problème de programmation mathématique
( P) Min f ( x )
Sujet à hi ( x ) ≤ bi i = 1,… , m
x ∈ Γ ⊂ Rn
où Γ est un ensemble convexe borné et f , hi , i = 1,… m, sont des
fonctions convexes sur Γ.
Définissons une premiere approximation de ( P ) en utilisant les
 k k 
points  x ∈ R : x = ∑ α j x ; ∑ α j = 1; α j ≥ 0, j = 1,… , k  ↔ Γ
n j

 j =1 j =1 
 k 
Γ x1 ( AP ) Min f  ∑ α j x j

5 x2  j =1 
x
 k 
Sujet à hi  ∑ α j x  ≤ bi ; i = 1,… , m
j
x 4 x3  j =1 
 
k
∑α j = 1
j =1
α j ≥ 0 ; j = 1,… , k
  k  Pour obtenir une approximation
( AP ) Min f  ∑ α j x j
linéaire ( ALP ) remplaçons
 j =1 
 k   k  k

Sujet à hi  ∑ α j x  ≤ bi ; i = 1,… , m
 j =1
j
  j =1
j
 ( )
f  ∑α j x  → ∑α j f x j
    j =1
k  k  k
∑α j = 1  j =1
j
 ( )
hi  ∑ α j x  → ∑ α j hi x j
j =1   j =1
α j ≥ 0 ; j = 1,… , k

k
( ALP ) Min ∑ j
α f x j
( )
j =1
k
Sujet à ∑ α j hi ( x j ) ≤ bi ; i = 1,… , m
j =1
k
∑α j = 1
j =1
α j ≥ 0 ; j = 1,… , k
 k
( ALP ) Min ∑ j
α f x j
( )
j =1
k
Sujet à ∑ α j hi ( x j ) ≤ bi ; i = 1,… , m
j =1
k
∑α j = 1
j =1
α j ≥ 0 ; j = 1,… , k

ou l'équivalent ( ALP ) Min ∑ j

α f x j
( )
j =1
k
Sujet à − ∑ α j hi x j ≥ −bi ; i = 1,… , m
( )
j =1
k
− ∑ α j = −1
j =1
α j ≥ 0 ; j = 1,… , k
Tout comme dans le cas linéaire, l'ensemble des points x1 ,… , x k{ }
est généré itérativement à mesure que chacun de ces derniers
devient intéressant pour réduire la valeur de la fonction
économique de ( ALP ) .
La procédure de résolution est amorcée avec un premier point x1
pour définir un premier problème restreint de ( ALP ) .

À une itération générale, nous disposons d'un ensemble de points

dont les indices appartiennent à un ensemble G pour définir le
problème restreint ( RALPG ) .
x1
k
Γ
x5
x 2 ( ALP ) Min ∑α j f ( x j )
j =1
k
x 4 x3 Sujet à − ∑ α j hi x j ≥ −bi ; i = 1,… , m
( )
j =1
k
− ∑ α j = −1
j =1
α j ≥ 0 ; j = 1,… , k
À une itération générale, nous disposons d'un ensemble de points
dont les indices appartiennent à un ensemble G pour définir le
problème restreint ( RALPG ) .
k
( ALP ) Min ∑α j f ( x j )
j =1
k
Sujet à − ∑ α j hi x j ≥ −bi ; i = 1,… , m
( )
j =1
k
− ∑ α j = −1
j =1
α j ≥ 0 ; j = 1,… , k

( RALPG ) Min ∑α j f (x j )
j∈G

Sujet à − ∑ α j hi x j ≥ −bi ; i = 1,… , m

( )
j∈G

− ∑ α j = −1
j∈G
α j ≥ 0 ; j ∈G
 Tout comme dans le cas linéaire, l'ensemble des points x1 ,… , x k { }
est généré itérativement à mesure que chacun de ces derniers
devient intéressant pour réduire la valeur de la fonction
économique de ( ALP ) . Initialisation. Determinons un premier problème restreint de ( ALP )
La procédure de résolution est amorcée avec un premier point x1 ∈ Γ
pour résoudre un problème auxiliaire ( ALPA ) et déterminer un ensemble
de points de Γ définissant un premier problème restreint de ( ALP ) .
À une itération générale, nous disposons d'un ensemble de points
dont les indices appartiennent à un ensemble G pour définir le
problème restreint ( RALPG ) .
x1
k
Γ
x5
x 2 ( ALP ) Min ∑α j f ( x j )
j =1
k
x 4 x3 Sujet à − ∑ α j hi x j ≥ −bi ; i = 1,… , m
( )
j =1
k
Étape 1. Résoudre le problème (RALPG ).
− ∑ α j = −1
j =1
α j ≥ 0 ; j = 1,… , k
À une itération générale, nous disposons d'un ensemble de points
dont les indices appartiennent à un ensemble G pour définir le
problème restreint ( RALPG ) .
k
( ALP ) Min ∑α j f ( x j )
j =1
Étape 1. Résoudre le problème (RALPG ).
k
Sujet à − ∑ α j hi x j ≥ −bi ; i = 1,… , m
( )
j =1
k
− ∑ α j = −1
j =1
α j ≥ 0 ; j = 1,… , k

( RALPG ) Min ∑α j f (x j )
j∈G

Sujet à − ∑ α j hi x j ≥ −bi ; i = 1,… , m

( )
j∈G

− ∑ α j = −1
j∈G
α j ≥ 0 ; j ∈G
Étape 1. Résoudre le problème (RALPG ).
Déterminons une solution optimale de (RALPG )
et les multiplicateurs optimaux correspondants.

( RALPG ) Min ∑α j f (x j )
j∈G

Sujet à − ∑ α j hi x j ≥ −bi ; i = 1,… , m

( ) πi
j∈G

− ∑ α j = −1 π0
j∈G
α j ≥ 0 ; j ∈G
Résolvons le problème ( RALPG ) avec l'algorithme du simplexe.
Soit
α une solution de base optimale
π T = [π1 ,… , π m , π0 ] le vecteur de multiplicateurs optimaux
Dénotons par ξ j le coût relatif de la variable α j , j ∈ G :
m
( ) ( )
ξ j = f x j + ∑ πi hi x j + π0 ≥ 0
i =1
j ∈ G.
 k
( ALP ) Min ∑ j
α f x j
( )
j =1
k
Sujet à − ∑ α j hi x j ≥ −bi ; i = 1,… , m
( ) πi
j =1
k
− ∑ α j = −1 π0
j =1
α j ≥ 0 ; j = 1,… , k

Dénotons par ξ j le coût relatif de la variable α j , j ∈ G :

m
( ) j

i =1
( )
ξ j = f x + ∑ πi hi x j + π0 ≥ 0 j ∈ G.

Étape 2. Mécanisme de vérification: Vérifier si la solution est optimale pour ( ALP)

en vérifiant si les coûts relatifs des autres variables dont les indices j ∉ G
sont aussi non négatifs:

Si ξ j ≥ 0 pour tout j ∈ {1,… , k } , alors la solution α j , j ∈ G et

α j = 0, j ∉ G, est optimale pour le problème ( ALP ) .
Étape 2. Mécanisme de vérification: Vérifier si la solution est optimale pour ( ALP)
en vérifiant si les coûts relatifs des autres variables dont les indices j ∉ G
sont aussi non négatifs.
Pour y arriver, résoudre un sous-problème defini à partir des coûts relatifs.
 k
( ALP ) Min ∑ j
α f x j
( )
j =1
k
Sujet à − ∑ α j hi x j ≥ −bi ; i = 1,… , m
( ) πi
Étape 2. Mécanisme de vérification: Vérifier si la solution est optimale pour ( ALP)
j =1
en vérifiant si les coûts relatifs des autres variables dont les indices j ∉ G
k
sont aussi non négatifs.
∑
− α = −1
Pour y arriver, résoudre un sous-problème definij à partir des coûts relatifs.
π0
j =1
α j ≥ 0 ; j = 1,… , k

Puisque les points x j , j ∉ G, ne sont pas connus à l'avance, nous

allons vérifier si le coût relatif
m
( )j

i =1
( )
ξ j = f x + ∑ πi hi x j + π0 ≥ 0 j ∉G

en déterminant la solution optimale xα du sous-problème suivant

défini sur Γ:
m  m 
( )
α 
α
( )
f x + ∑ πi hi x + π0 = Min  f ( x ) + ∑ πi hi ( x ) + π0  .
i =1
x∈Γ
 i =1 
Puisque les points x j , j ∉ G, ne sont pas connus à l'avance, pour
vérifier si le coût relatif
m
( )
ξ j = f x + ∑ πi hi x j + π0 ≥ 0
j

i =1
( ) j ∉G

en déterminant la solution optimale xα du sous-problème suivant

défini sur Γ:
m  m 
( )
α 
α
( )
f x + ∑ πi hi x + π0 = Min  f ( x ) + ∑ πi hi ( x ) + π0  .
i =1
x∈Γ
 i =1 
Étape 2. Mécanisme de vérification: Vérifier si la solution est optimale pour ( ALP)
en vérifiant si les coûts relatifs des autres variables dont les indices j ∉ G
sont aussi non négatifs.
Pour y arriver, résoudre un sous-problème defini à partir des coûts relatifs.
Si la valeur optimale est non négative, alors nous avons une solution optimale
de ( ALP), et la procédure s'arrête.

Si
m
( )
f x α

i =1
( )
+ ∑ πi hi xα + π0 ≥ 0

alors ξ j ≥ 0 pour tout j ∈ {1,… , k } , et par conséquent la solution

α j , j ∈ G et α j = 0, j ∉ G, est optimale pour le problème ( ALP ) .
 Puisque les points x j , j ∉ G, ne sont pas connus à l'avance, pour
vérifier si le coût relatif
m
( )j

i =1
( )
ξ j = f x + ∑ πi hi x j + π0 ≥ 0 j ∉G

en déterminant la solution optimale xα du sous-problème suivant

défini sur Γ:
m  m 
( )
α 
α
( )
f x + ∑ πi hi x + π0 = Min  f ( x ) + ∑ πi hi ( x ) + π0  .
i =1
x∈Γ
 i =1 
Étape 3. Sinon, xα est un point de Γ dont l'indice n'appartient
pas à [Link] son indice dans un ensemble V .
Min
Min ∑ αα jj ff ( xxjj ) + αα f ( xα )
jj∈
∈GG

Définissons l'ensemble D = Φ. Sujet àà −− ∑ α

Sujet ( ) ( )
α jjhhii xx jj −≥α−αbhi i; i x=α1,…
≥ −, m
bi ; i = 1,… , m
Si jj∈
∈GG
Étape 4. Remplacer G par G′ = G ∪ V −m D −− ∑ α
α jj −=α−α1 = −1
et reprendre l'étape 1.
( ) ∑
f xα + π
i =1
i hi ( x ) + π
α
0 <0 jj∈
∈GG
αα jj ≥≥ 00 ;; jj∈
∈GG, αα ≥ 0

alors le point xα devient un nouveau point utilisé pour améliorer

l'approximation de Γ et ainsi définir un nouveau problème restreint
en introduisant une nouvelle colonne associée à xα et la variable
correspondante α α dans le problème restreint actuel.
 Γ est un ensemble convexe borné et f , hi , i = 1,… m,
Théorème: Si sont desfonctions convexes sur Γ
m  m 
( ) + ∑ π h ( x )
f x α
i i
α
+ π 0 = Min  f ( x ) + ∑ π i hi ( x ) + π 0  ≥ 0,
  
i =1
x∈Γ
 i =1 
alors
x = ∑ α j x j (P) Min f ( x )
Sujet à hi ( x ) ≤ bi i = 1,… , m
j∈G
est solution optimale de ( P ) . x∈ Γ ⊂ Rn

Preuve. Démontrons d'abord que x est une solution réalisable

de ( P ) à cause des hypothèses de convexité. En effet,
x = ∑ α j x j , ∑ α j = 1, α j ≥ 0, j ∈ G
j∈G j∈G
impliquent que x ∈ Γ puisque Γ est convexe.

De plus, puisque hi est convexe pour tout i = 1, …, m, il s'ensuit

 
 j∈G
j
 j∈G ( )
hi ( x ) =hi  ∑ α j x  ≤ ∑ α j hi x j ≤ bi i = 1, …, m,
 
et ainsi x est réalisable pour le problème original ( P ) .
Pour démontrer que x est optimale pour ( P ) , nous nous
appuyons sur la dualité forte linéaire et sur la dualité faible
lagrangienne.

( RALPG ) Min ∑α j f (x j )
j∈G

Sujet à − ∑ α j hi x j ≥ −bi ; i = 1,… , m

( ) πi
j∈G

− ∑ α j = −1 π0
j∈G
α j ≥ 0 ; j ∈G
Par la dualité forte linéaire, nous avons que
 m 
∑ j 
α f ( )
x j
= − ∑ i i π b + π 0 .
j∈G  i =1 
Ainsi puique f est convexe, alors
   m 
 j∈G  j∈G ( )
f ( x ) = f  ∑ α j x  ≤ ∑ α j f x = −  ∑ πi bi + π0 
j j

   i =1 
Pour démontrer que x est optimale pour ( P ) , nous nous
appuyons sur la dualité forte linéaire et sur la dualité faible
lagrangienne.

( RALPG ) Min ∑α j f (x j )
j∈G

Sujet à − ∑ α j hi x j ≥ −bi ; i = 1,… , m

( ) πi
j∈G

− ∑ α j = −1 π0
j∈G
α j ≥ 0 ; j ∈G

T
Puisque [π1 ,… , π m , π0 ] est une solution optimale du dual
T
linéaire de ( RALPG ) , il s'ensuit que [π1 ,… , π m ] ≥ 0.
 T
Puisque [π1 ,… , π m , π0 ] est une solution optimale du dual
T
linéaire de ( RALPG ) , il s'ensuit que [π1 ,… , π m ] ≥ 0.
Considérant le dual lagrangien de ( P ) :

( P) Min f ( x )   m 
Max Inf f ( x ) + ∑ λi ( hi ( x ) − bi ) 
Sujet à hi ( x ) ≤ bi i = 1,… , m λ ≥0  x∈Γ  
 i =1
n
x∈Γ ⊂ R
T
il s'ensuit que [π1 ,… , π m ] ≥ 0 est une solution réalisable du dual
lagrangien de ( P ) .
Se référant au théorème de dualité lagrangienne faible, alors
pour toute solution xˆ de ( P ) ,
 m 
f ( xˆ ) ≥ Inf  f ( x ) + ∑ πi ( hi ( x ) − bi ) 
x∈Γ
 i =1 
m  m 
≥ −∑ πi bi + Min  f ( x ) + ∑ πi hi ( x ) 
i =1
x∈Γ
 i =1 
Se référant au théorème de dualité lagrangienne faible, alors
pour toute solution xˆ de ( P ) ,
m  m 
f ( xˆ ) ≥ −∑ πi bi + Min  f ( x ) + ∑ πi hi ( x ) 
i =m1
x∈Γ
 m i =1 
( ) ( )
≥ −∑ πi bi + f xα + ∑ πi hi xα
i =1 i =1
( par définition de xα )
m
≥ −∑ πi bi − π0 puisque par hypothèse du théorème
i =1
m
( )
f x α

i =1
( )
+ ∑ πi hi xα + π0 ≥ 0
m
ou ( ) + ∑ π h ( xα ) ≥ −π
f x α

i =1
i i

0

≥ f ( x ) puisque par la dualité linéaire forte

 m 
f ( x ) ≤ −  ∑ π i bi + π 0 
  
 i =1 

Donc f ( xˆ ) ≥ f ( x ) pour toute solution réalisable xˆ de ( P ) . 

 Bornes sur la valeur optimale de (P)
À chaque itération du processus, nous engendrons des bornes
inférieure et supérieure sur la valeur optimale f * de ( P ) .
En effet, même si le critère d'optimalité
m  m 
( ) ( )
f x + ∑ πi hi x + π0 = Min  f ( x ) + ∑ πi hi ( x ) + π0  ≥ 0,
α α

i =1
x∈Γ
 i =1 
n'est pas saisfait, la première partie du théorème précédent tient
pour démontrer que
x = ∑ α j x j
j∈G
est réalisable pour ( P ) .
Théorème: Si
m  m 
( ) + ∑ π h ( x )
f x α
i i
α
+ π0 = Min  f ( x ) + ∑ πi hi ( x ) + π0  ≥ 0,
i =1
x∈Γ
 i =1 
alors
x = ∑ j

α x j

j∈G
est solution optimale de ( P ) .

Preuve. Démontrons d'abord que x est une solution réalisable

de ( P ) à cause des hypothèses de convexité. En effet,
x = ∑ α j x j , ∑ α j = 1, α j ≥ 0, j ∈ G
j∈G j∈G
impliquent que x ∈ Γ puisque Γ est convexe.

De plus, puisque hi est convexe pour tout i = 1, …, m, il s'ensuit

 
 j∈G
j
 j∈G ( )
hi ( x ) =hi  ∑ α j x  ≤ ∑ α j hi x j ≤ bi i = 1, …, m,
 
et ainsi x est réalisable pour le problème original ( P ) .
À chaque itération du processus, nous engendrons des bornes
inférieure et supérieure sur la valeur optimale f * de ( P ) .
En effet, même si le critère d'optimalité
m  m 
( ) ( )
f x + ∑ πi hi x + π0 = Min  f ( x ) + ∑ πi hi ( x ) + π0  ≥ 0,
α α

i =1
x∈Γ
 i =1 
n'est pas saisfait, la première partie du théorème précédent tient
pour démontrer que
x = ∑ α j x j
j∈G
est réalisable pour ( P ) .

Par conséquent f * ≤ f ( x ) .
À chaque itération du processus, nous engendrons des bornes
inférieure et supérieure sur la valeur optimale f * de ( P ) .
Par conséquent f * ≤ f ( x ) .
T
Également, puisque [π1 ,… , π m , π0 ] est une solution optimale du dual
T
linéaire de ( RALPG ) , il s'ensuit que [π1 ,… , π m ] ≥ 0
( P) Min f ( x )
( RALPG ) Min
j∈G
( )
∑α j f xj Sujet à hi ( x ) ≤ bi i = 1,… , m
x ∈ Γ ⊂ Rn
( )
Sujet à − ∑ α j hi x j ≥ −bi ; i = 1,… , m πi
j∈G

− ∑ α j = −1 π0   m 
j∈G Max Inf  f ( x ) + ∑ λi ( hi ( x ) − bi ) 
λ ≥o  x∈Γ
α j ≥ 0 ; j ∈G   i =1 
T
et ainsi [π1 ,… , π m ] ≥ 0 est une solution réalisable du dual
lagrangien de ( P ) .
À chaque itération du processus, nous engendrons des bornes
inférieure et supérieure sur la valeur optimale f * de ( P ) .
Par conséquent f * ≤ f ( x ) .
T
Également, puisque [π1 ,… , π m , π0 ] est une solution optimale du dual
T
linéaire de ( RALPG ) , il s'ensuit que [π1 ,… , π m , π0 ] ≥ 0
T
et ainsi [π1 ,… , π m ] est une solution réalisable du dual
lagrangien de ( P ) .
Par conséquent
m m
g (π ) = −∑ πi bi + f x( )
α
+ ∑ πi hi xα
( )
i =1 i =1
m  m 
= −∑ πi bi + Min  f ( x ) + ∑ πi hi ( x )  ≤ f *
i =1
x∈Γ
 i =1 
Par conséquent f * ≤ f ( x ) .

Par conséquent
m m
g (π ) = −∑ πi bi + f x
( )
α
+ ∑ πi hi xα
( )
i =1 i =1
m  m 
= −∑ πi bi + Min  f ( x ) + ∑ πi hi ( x )  ≤ f *
i =1
x∈Γ
 i =1 

Ainsi, si fˆ et gˆ dénotent respectivement la valeur de la meilleure

solution de ( P ) et celle de la meilleure solution de son dual
rencontrées jusqu'ici lors de la résolution, alors
gˆ ≤ f * ≤ fˆ .
De ceci découle le critère d'arrêt suivant pour identifier une
solution ε -optimale de ( P ) :
fˆ − gˆ ≤ ε .
 Convergence

Puisque le nombre de points nécessaires pour approximer Γ

par leur enveloppe convexe n'est pas nécessairement fini, il
s'ensuit que la preuve basée sur la stratégie de restriction
développée pour le cas linéaire ne tient plus nécessairement!
 Advantages

• Solve a sequence of restricted (smaller) problems

• Mechanism to verify if the optimal solution of restricted

problem is optimal for the original problem: solving a
problem specified with the nice constraints
• Same mechanism generates additional variables to
modify the restricted problem and to get closer to the
original one
 Advantage of the approach

• PRIMAL METHOD:
for any restricted problem

the optimal solution λi*, iεG

x = ∑ iεG λi* xi feasible for the original problem

P.L. Jackson, D.F. Lynch, "Revised Dantzig-Wolfe Decomposition"
Mathematical Programming 39 (1987), 157-179

[6] G.B. Dantzig, P. Wolfe,"Decomposition Principle for Linear

Programs", Operations Research 8 (1960 ) ,101 − 110
La méthode de Dantzig-Wolfe illustre bien une approche de
résolution par "génération de colonnes".

Dans cette méthode, nous avons d'abord besoin d'identifier un

problème équivalent où la génération de colonnes s'appliquent.

Après avoir résolu une restriction du problème définie avec un

sous ensemble de variables (dont les indices sont dans G ), le
mécanisme pour vérifier si la solution optimale de cette restriction
est en fait une solution optimale du problème défini à partir
des contraintes "faciles" à traiter.

Dans le cas où la solution n'est pas optimale pour le problème,

le mécanisme génère du même coup de l'information permettant
de définir une nouvelle variable dont l'introduction dans une
nouvelle restriction entrainera une meilleure valeur optimale.
Situations où l'approche de resolution avec "génération de colonnes"
peut devenir intéressante:

le sous problème utilisé comme mécanisme (pour vérifier si la

solution d'une restriction est effectivement une solution pour le
problème à résoudre) possède une structure permettant de le
résoudre "facilement"

le problème à résoudre comporte un très grand nombre de variables

qu'il est difficile de déterminer à priori, mais qu'il est facile de générer
en solutionnant le sous problème définissant le mécanisme lorsqu'elles
deviennent pertinentes pour réduire la valeur de la fonction économique.
 References

• M. S. Bazaraa, J.J. Jarvis, H.D. Sherali, ‘Linear

Programming and Network Flows’, Third Edition, Wiley
(2005).

• G.B. Dantzig, P. Wolfe, ‘Decomposition Principle for

Linear Programs’, Operations Research 8 (1960), 101-
111.
• A.M. Geoffrion, ‘Elements of Large Scale Mathematical
Programming, Part I: Concepts; Part II: Synthesis of
Algorithms and Bibliography’,Management Science 16
(1970), 652-691.