Cours : Décomposition de Dantzig-Wolfe

Nizar El Hachemi

11 décembre 2022

Nizar El Hachemi Cours : Décomposition de Dantzig-Wolfe

Introduction

La méthode de Dantzig-Wolfe (DW) peut-être utilisée pour

résoudre les problèmes de grande taille dont les contraintes
principales se séparent en deux groupes comme suit dans le PNE
(PX) :

Min c t x (1)
x
sujet à : (2)
Ax = b (3)
Dx = e (4)
x ∈ Nn (5)
Où x est le vecteur des variables ; c ∈ Rn ; b ∈ Zm ; e ∈ Zm ;
′

A ∈ Zm ∗ Zn et D ∈ Zm ∗ Zn sont des vecteurs et des matrices de

′

scalaires.
Nizar El Hachemi Cours : Décomposition de Dantzig-Wolfe
Introduction

Un des deux groupes de contraintes (Dx = e ) doit posséder une

structure particulière telle que, si l'autre groupe est omis, le PNE
est nettement plus facile à résoudre. Par exemple, les contraintes
faciles (Dx = e ) combinées aux contraintes x ∈ Nn peuvent avoir
la structure des contraintes d'un ou plusieurs problèmes de ots à
coût minimun, de plus court chemin, de sac à dos, chaque problème
étant restreint à un sous ensemble de variables qui lui est propre.
Lorsque x peut se partitionner en l sous-ensembles disjoints de
variables x = (x1 , ..., xl ) tels que les contraintes Dx = e et x ∈ Nn
peuvent s'écrire comme l sous-ensembles de contraintes Dxk = ek ,
xk ∈ Nnk , k ∈ K = {1, ..., l}, on dit que ces contraintes sont
séparables et qu'elles ont une structure bloc-angulaire.

Nizar El Hachemi Cours : Décomposition de Dantzig-Wolfe

Introduction

Les contraintes diciles (Ax = b) sont souvent appelées

contraintes liantes ou contraintes globales car elles impliquent des
variables provenant de plusieurs des sous-ensembles disjoints.
On note que la décomposition de Dantzig-Wolfe peut aussi
s'appliquer à certains problèmes non-linéaires.

Nizar El Hachemi Cours : Décomposition de Dantzig-Wolfe

Exemple de problème décomposable selon DW : Problème
de découpe

Une companie de papier doit satisfaire les demandes dj , j ∈ J , pour

des petits rouleaux de largeur lj qui doivent être découpés dans un
ensemble U de grands rouleaux de largeur L. Il faut déterminer les
patrons de coupe des grands rouleaux de largeur L de façon à
satisfaire la demande tout en minimisant le nombre de grands
rouleaux découpés. Ce problème se formule en utilisant les variables
suivantes :
Yu est une variable binaire qui vaut 1 si le grand rouleau
u ∈ U est découpé.
Xju le nombre de petits rouleaux de largeur lj , j ∈ J , découpés
dans le grand rouleau u ∈ U .

Nizar El Hachemi Cours : Décomposition de Dantzig-Wolfe

Formulation

(6)
X
Min Yu
X ,Y
u∈U
sujet à : (7)
(8)
X
Xju ≥ dj , ∀j ∈ J
u∈U

(9)
X
lj Xju ≤ LYu , ∀u ∈ U
j∈J
Yu ∈ {0, 1}, ∀u ∈ U (10)
Xju ∈ N, ∀j ∈ J, ∀u ∈ U (11)
Cette formulation a une structure bloc-angulaire. Le premier bloc
de contraintes 8 représente les contraintes liantes alors que les
contraintes 9-11 se séparent par rouleau u et présentent la
structure d'un petit PNE pour chaque grand rouleau.
Nizar El Hachemi Cours : Décomposition de Dantzig-Wolfe
Théorème de Minkowski

Considérons le polyèdre P = {x ∈ Rn |Ax ≤ b} = ̸ ∅.

Dénition : un vecteur r ∈ Rn est un rayon de P si
∀x ∈ P, ∃α ≥ 0 tel que x + αr ∈ P .
Dénition : un vecteur r est un rayon extrême de P s'il est
impossible de trouver deux rayons r 1 et r 2 de P linéairement
indépendant de sorte que r = 12 r 1 + 21 r 2 .
Notons que les points extrêmes et les rayons extrêmes de P
permettent de représenter complètement P .

Nizar El Hachemi Cours : Décomposition de Dantzig-Wolfe

Théorème de Minkowski

Soit V = {v1 , v2 , ...vk } = EXT (P) l'ensemble des points extrêmes

de P , R = {r1 , r2 , ..., rl } l'ensemble des rayons extrêmes de P et
k l k
λj = 1, λ ∈ R+k , α ∈ R+l }. Si
P P P
Q={ λi vi + αj rj |
i=1 j=1 i=1
rang (A) = n alors P = Q .

Nizar El Hachemi Cours : Décomposition de Dantzig-Wolfe

Principe de la décomposition de DW

Le principe de la décomposition de DW permet de réécrire le PNE

(PX) sous la forme d'un autre PNE qui contient seulement les
contraintes liantes Ax = b et une ou plusieurs contraintes de
convexité, mais un très grand nombre de variables. Les contraintes
faciles Dx = e permettent de dénir les nouvelles variables.
Considérons l'enveloppe convexe conv (∆) du domaine réalisable
∆ = {x|Dx = e, x ∈ Nn }, et supposons que ∆ ̸= ∅. Dans ce cas,
le théorème de Minkowski s'énnonce comme suit :
Théorème : un point x ∈ conv (∆) si et seulement s'il peut s'écrire
comme une combinaison convexe des points extrêmes de conv (∆)
plus une combinaison linéaire (avec des poids non-négatives) de ses
rayons extrêmes.

Nizar El Hachemi Cours : Décomposition de Dantzig-Wolfe

Principe de la décomposition de DW

(12)
X X
x= θp ωp + λr ρr
p∈Ω r ∈Γ

θp = 1 (13)
X

p∈Ω
θp ≥ 0, ∀p ∈ Ω et λr ≥ 0, ∀r ∈ Γ (14)
où Ω est l'ensemble des indices des points extrêmes de conv (∆),
ωp est le p ième point extrême et θp est le poids associé à ce point
extrême. Γ est l'ensemble des indices des rayons extrêmes conv (∆),
ρr est le r ième rayon extrême et λr est le poids associé à ce rayon
extrême.

Nizar El Hachemi Cours : Décomposition de Dantzig-Wolfe

Principe de la décomposition de DW

Le vecteur x peut donc être remplacé dans la fonction objectif et

les contraintes liantes du PNE. Les contraintes Dx = e et x ≥ 0
sont directement prises en compte dans la dénition des nouvelles
variables. Les contraintes d'intégrité ne le sont pas et doivent donc
demeurer sur les variables x . Le changement de variables en
question permet d'obtenir le modèle suivant :

Nizar El Hachemi Cours : Décomposition de Dantzig-Wolfe

Principe de la décomposition de DW

(15)
X X
Min c t ( θp ωp + λr ρr )
x,θ,λ
p∈Ω r ∈Γ
sujet à : (16)
(17)
X X
A( θp ωp + λr ρ r ) = b
p∈Ω r ∈Γ

θp = 1 (18)
X

p∈Ω
θp ≥ 0, ∀p ∈ Ω (19)
λr ≥ 0, ∀r ∈ Γ (20)
λr ρr , entiers. (21)
X X
x= θ p ωp +
p∈Ω r ∈Γ

En réarrangeant certains termes et en posant que : cp = c t ωp ,

cr = c t ρr , ap = Aωp et ar = Aρr
Nizar El Hachemi Cours : Décomposition de Dantzig-Wolfe
Principe de la décomposition de DW

(22)
X X
Min c p θp + cr λr
x,θ,λ
p∈Ω r ∈Γ
sujet à : (23)
a p θp + ar λr = b (24)
X X

p∈Ω r ∈Γ

θp = 1 (25)
X

p∈Ω
θp ≥ 0, ∀p ∈ Ω (26)
λr ≥ 0, ∀r ∈ Γ (27)
λr ρr , entiers. (28)
X X
x= θp ωp +
p∈Ω r ∈Γ

Ce nouveau PNE est appelé problème maître (PM), il est

équivalent au (PX). En général, il comporte moins de contraintes
mais beaucoup plus de variables, soit une par point extrême et
rayon extrême du domaine ∆.
Principe de la décomposition de DW
Lorsque Dx = e est séparable par sous-ensembles disjoints de
variables x = (x1 , x2 , ..., xl ), on dénit un domaine
∆k = {xk |Dk xk = ek , xk ∈ Nnk }, ∀k ∈ K et des ensembles de
points et rayons extrêmes correspondants. Le PM devient comme
suit :
(29)
X X X
Min ( cpk θpk + crk λrk )
x,θ,λ
k∈K p∈Ωk r ∈Γk
sujet à : (30)
apk θpk + ark λrk ) = b (31)
X X X
(
k∈K p∈Ωk r ∈Γk

θpk = 1, ∀k ∈ K (32)
X

p∈Ωk
θpk ≥ 0, ∀k ∈ K , ∀p ∈ Ωk (33)
λrk ≥ 0, ∀k ∈ K ∀r ∈ Γk (34)
λrk ρrk , entiers, ∀k ∈ K (35)
X X
xk = θpk ωpk +
p∈Ωk r ∈Γ
Nizar El Hachemi Cours : Décomposition de Dantzig-Wolfe
Décomposition de DW : problème de découpe

Concernant le problème de découpe, les contraintes faciles se

séparent par grand rouleau u ∈ U . Il y a donc un domaine ∆u par
rouleau u . Ce domaine étant borné, il ne dispose pas de rayons
extrêmes. Chaque point extrême ωpu correspond à un plan de
coupe associé au grand rouleau u . ωpu = (Ypu , Xp1u , ..., Xp|J|u ),
d'après le principe de décomposition de DW,
θpu ωpu . Soit
P
(Yu , X1u , ..., X|J|u ) =
p∈Ωu
x = (Y1 , X11 , ..., X|J|1 , ..., Y|U| , X|J|1 , ..., X|J||U| ) le vecteur de
décision associé au problème de découpe et le vecteur coût associé
est c t = (1, 0..., 0, 1, 0, ..., 0, 1, ..., 0, ..., 0, 1, 0, ..., 0). Ainsi, pour un
patron de coupe diérent du patron nul est
cpu = (1, 0, ..., 0).(Ypu , Xp1u , ..., Xp|J|u )t où Ypu = 1. On en déduit
que :

Nizar El Hachemi Cours : Décomposition de Dantzig-Wolfe

Décomposition de DW : problème de découpe

(36)
X X
Min θpu
X ,Y ,θ
u∈U p∈Ωu \{0}
sujet à : (37)
(38)
X X
j
apu θpu ≥ dj , ∀j ∈ J
u∈U p∈Ωu

θpu = 1, ∀u ∈ U (39)
X

p∈Ωu
θpu ≥ 0, ∀u ∈ U, ∀p ∈ Ωu (40)
θpu , entiers, ∀j ∈ J ∀u ∈ Ωu (41)
X
j
Xju = apu
p∈Ωu

θpu ∈ {0, 1} ∀u ∈ U (42)

X
Yu =
p∈Ωu \{0}

Notons que apuj

est le nombre de rouleaux de largeur lj dans le
patron de coupe p . Le patron de coupe nul est associé à un vecteur
nul (Ypu , Xp1u , ..., Xp|J|u ) = (0, ..., 0).
Résolution par Branch-and-Price

An de simplier, considérons le cas où il existe un seul domaine ∆

borné (aucun rayon extrême). Le PM se formule comme suit :

(43)
X
Min c p θ p ωp
x,θ
p∈Ω
sujet à : (44)
(45)
X
ap θp ωp = b
p∈Ω

θp = 1 (46)
X

p∈Ω
θp ≥ 0, ∀p ∈ Ω (47)
θp ωp , entiers. (48)
X
x=
p∈Ω

Nizar El Hachemi Cours : Décomposition de Dantzig-Wolfe

Génération de Colonnes (GC)

La méthode de GC permet de résoudre des problèmes linéaires qui

comportent un très grand nombre de variables lorsque celles-ci
peuvent être générées à partir d'un Sous-Problème (SP). Un tel
programme est donné par la relaxation linéaire (43) − (47) du PM,
noté RLPM. An que la GC soit ecace, il faut que la résolution du
SP soit relativement facile car il devrait être résolu plusieurs fois. La
méthode de GC débute avec un problème maître restreint PMRi qui
contient un petit sous-ensemble Ωi des variables (au début, i = 1).

Nizar El Hachemi Cours : Décomposition de Dantzig-Wolfe

Génération de Colonnes (GC)
Ainsi, le PMRi est comme suit :

(49)
X
Min c p θ p ωp
θ
p∈Ωi
sujet à : (50)
(51)
X
ap θ p ωp = b
p∈Ωi

θp = 1 (52)
X

p∈Ωi

θp ≥ 0, ∀p ∈ Ωi (53)
Les autres variables θp ∈ Ω \ Ωi , aussi appelé colonnes seront
générées au besoin à l'aide d'un problème auxiliaire appelé
sous-problème (SP). La technique de la GC est un processus
itératif. A chaque itération i , on résout d'abord le PMRi , restreint à
Ωi et ensuite le SP.
Nizar El Hachemi Cours : Décomposition de Dantzig-Wolfe
Génération de Colonnes (GC)

La résolution du PMRi permet d'obtenir une solution réalisable

θi = {θpi }p∈Ωi . Elle permet aussi d'obtenir une solution duale
(π i , σ i ) associée à cette solution primale.
La question légitime à se poser est : sous quelles conditions θi sera
optimale pour le problème RLPM ? La réponse est simple, il faut
que le coût réduit de chacune des variables θp ∈ Ω \ Ωi soit ≥ 0.
Rappelons que le coût réduit associé à la j ième variable est
c̄j = cj − π t aj où aj est la j ième ligne de la matrice A. Dans notre
cas, le SP associè à l'itération i noté SP i est :

z SP = Min c t − π i Ax − σ i (54)
x
sujet à : (55)
Dx = e (56)
x≥0 (57)

Nizar El Hachemi Cours : Décomposition de Dantzig-Wolfe

Génération de Colonnes (GC)

Si ziSP est la valeur optimale du SPi est ≥ alors il n'y a aucune

variable non considérée θp ∈ Ω \ Ωi à coût réduit négatif. Par
conséquent, la solution optimale θi du PMRi est optimale la RLPM.
Sinon la solution optimale xi de SP i qui n'est rien d'autre qu'un
point extrême ωp permet de générer une nouvelle variable θp de
coût réduit négatif. Cette variable est alors ajoutée à Ωi pour
former Ωi+1 et un nouveau PMRi+1 . On recommence une nouvelle
itération en résolvant PMRi+1 .
Théorème : La méthode de GC converge en un nombre ni
d'itérations vers la solution optimale.
Preuve : Il y a un nombre ni de points extrêmes et de rayons
extrêmes. De plus, le SP ne peut pas générer deux fois la même
solution.

Nizar El Hachemi Cours : Décomposition de Dantzig-Wolfe

GC : problème de découpe
Pour le problème de découpe, la RLPM est la suivante :
(58)
X
Min θp
X ,Y ,θ
p∈Ω\{0}
sujet à : (59)
(60)
X
apj θp ≥ dj , ∀j ∈ J
p∈Ω
θp ≥ 0, ∀p ∈ Ω (61)
Notons que puisque les rouleaux sont identiques, on peut agréger
les variables θ selon l'équation suivante : θpu = θp , ∀p ∈ Ω De
P
u∈U
même, le SP dans ce cas devient :
(62)
X
lj Xj ≤ LY
j∈J
Y ∈ {0, 1} (63)
Xj ≥ 0, entiers, ∀j ∈ J (64)
Nizar El Hachemi Cours : Décomposition de Dantzig-Wolfe
GC : problème de découpe

Bien évidemment, le patron de coupe vide (Y , X ) = (0, 0) n'a

aucun intérêt. An de calculer le coût réduit de la variable θp
associée au patron de coupe p ∈ Ω \ Ωi , nous considéronsPles
variables πji associées aux contraintes 60. Ainsi c̄pi = 1 − api πji .
j∈J
Par conséquent, le SP i est comme suit :

Min 1 − πji Xj (65)

X

(66)
X
lj Xj ≤ L
j∈J
Xj ≥ 0, entiers, ∀j ∈ J (67)
Lorsqu'un patron de coupe p de coût réduit négatif est identié, la
variable θp associée est ajoutée au niveau du PM en xant les api au
nombre de rouleaux de largeur lj découpés dans le patron p .
Nizar El Hachemi Cours : Décomposition de Dantzig-Wolfe
Branchement

Les contraintes d'intégrité sont sur les variables x ce qui nous

amènent à dénir les règles de branchement. Le principe de la DW
permet de spécier comment traiter les contraintes d'intégrité, au
niveau du PM ou au niveau du SP.
Remarque : pour que la méthode soit exacte, il faut générer au
besoin des colonnes dans tous les noeuds de l'arbre d'énumeration.

Nizar El Hachemi Cours : Décomposition de Dantzig-Wolfe