Chapitre 5

Méthode de plans coupants

1. Algorithme générique de plans coupants

2. Inégalités de Chvátal-Gomory

3. Algorithme de Gomory

4. Plans coupants spécifiques

5. Branch-and-cut pour le problème de sac à dos

Chapitre 5 : Méthode de plans coupants 5.2

5.1 Algorithme générique de plans coupants

Soit S un ensemble discret. On a vu à la Section 4.1 que

min cTx = min cT x

x∈S x∈conv(S)

et à la Section 4.2 que conv(S) pouvait être décrit par

un ensemble fini d’inégalités valides.

À partir de la relaxation linéaire d’un PNE, une mé-

thode de plans coupants ajoute des inégalités valides
pour S afin de construire conv(S) autour d’une solu-
tion optimale de PNE.

Voyons un algorithme générique de plans coupants.

Notation :

X ⊇ conv(S) : domaine de la relaxation linéaire de PNE

k : compteur d’itérations

X k : domaine réalisable à l’itération k

Rk : relaxation à l’itération k ( min cTx)

x∈X k
Chapitre 5 : Méthode de plans coupants 5.3

1. Initialisation
• X 0 := X
• k := 0

2. Relaxation linéaire
• Résoudre Rk .
• Si une solution optimale de Rk est trouvée, noter
cette solution xk et sa valeur z k .

3. Test d’arrêt
• Si Rk est non réalisable, alors arrêter car PNE est
non réalisable
• Si Rk est non borné, alors arrêter car PNE est non
borné ou non réalisable
• Si xk est entière, alors arrêter xk est optimale pour
PNE

4. Hyperplan de séparation
• Trouver un hyperplan de séparation (π k )Tx = π0k
qui sépare xk de S
• En déduire une inégalité valide (π k )Tx ≤ π0k
Chapitre 5 : Méthode de plans coupants 5.4

5. Mise à jour
• X k+1 := {x ∈ X k | (π k )Tx ≤ π0k }
• k := k + 1
• Aller à l’étape 2

Remarques :
• À l’étape 4, l’hyperplan est appelé un plan coupant ou
une coupe car il permet d’éliminer xk
• Aux étapes 4 et 5, on peut trouver et ajouter plus
d’un plan coupant
• À l’étape 2, on utilise, en général, l’algorithme du sim-
plexe dual pour réoptimiser

Difficultés :
• Peut nécessiter un grand nombre d’itérations
• Souvent difficile de trouver un plan coupant

Pour les contourner, on combine cette méthode à un

algorithme d’énumération implicite (branch-and-cut) :
Au besoin et si on en trouve, on ajoute des plans cou-
pants après avoir résolu toutes (ou certaines) relaxations
linéaires dans l’arbre d’énumération
Chapitre 5 : Méthode de plans coupants 5.5

5.2 Inégalités de Chvátal-Gomory (C-G)

Considérons le PNE suivant :

(P N E) z = min cT x
x
sujet à : Ax ≤ b
x ∈ Nn

avec A ∈ Zm×n et b ∈ Zm. Dénotons par ATi = (Aij )j=1,...,n

une ligne de A et posons S = {x ∈ Nn | Ax ≤ b}.

Théorème: Soit ATi x ≤ bi, i = 1, . . . , m, des inégalités

valides pour S. Quelque soit u ∈ Rm
+ , l’inégalité π x ≤
T

m m
n
P P
π0 avec π = b uiAic ∈ Z et π0 = b uibic ∈ Z est
i=1 i=1
une inégalité valide pour S, appelée inégalité de C-G.

Preuve : Soit x ∈ S. Alors

m
X m
X m
X
πTx = b uiATi cx ≤ uiATi x ≤ u i bi
i=1 i=1 i=1
m
X
⇒ πTx ≤ b u i bi c = π0 .
i=1


Chapitre 5 : Méthode de plans coupants 5.6

Remarques :
• Chaque contrainte ATi x ≤ bi, i = 1, . . . , m, de PNE
est une inégalité valide pour S.
• Pour une contrainte d’égalité ATi x = bi, ui ∈ R est
quelconque.

Exemples : Soit

S = {x ∈ N2|−2x1+x2 ≤ 1, 2x1+x2 ≤ 3, −x1 ≤ 0, −x2 ≤ 0}.

Ainsi, n = 2, m = 4, AT1 = (−2, 1), b1 = 1, AT2 = (2, 1),

b2 = 3, AT3 = (−1, 0), b3 = 0, AT4 = (0, −1) et b4 = 0.

 
1 1 3
u = (0, , 0, ) ⇒ x1 + 0x2 ≤
2 2 2
⇒ x1 ≤ 1
     
4 3 8 6 4 3 4 9
u = ( , , 0, 0) ⇒ − + x1 + + x2 ≤ +
7 7 7 7 7 7 7 7
⇒ −x1 + x2 ≤ 1
     
2 6 4 12 2 6 2 18
u = ( , , 0, 0) ⇒ − + x1 + + x2 ≤ +
7 7 7 7 7 7 7 7
⇒ x 1 + x2 ≤ 2
Chapitre 5 : Méthode de plans coupants 5.7

Posons
Xm m
X
X 1 = {x ∈ Rn | b uiATi cx ≤ b uibic, ∀u ∈ Rm
+ }.
i=1 i=1

Remarques :
• Puisque A ∈ Zm×n et b ∈ Zm, les contraintes initiales
sont comprises dans la définition de X 1.
• X 1 est le domaine obtenu par l’ajout de toutes les
inégalités C-G.
• S ⊆ conv(S) ⊆ X 1.

À partir de l’exemple précédent, on montre que, dans

certains cas, conv(S) ⊂ X 1, i.e., X 1 6= conv(S).

En effet, montrons qu’il n’existe pas u ∈ R4+ tel que

( 12 , 23 ) peut être éliminé par une inégalité C-G, i.e.,
1 3
b−2u1 + 2u2 − u3c +bu1 + u2 − u4c ≤ bu1 + 3u2c , ∀u ∈ R4+.
2 2

Comme b−2u1 + 2u2 − u3c ≤ b−2u1 + 2u2c et

bu1 + u2 − u4c ≤ bu1 + u2c, il est suffisant de montrer
que

b−2u1 + 2u2c + 3 bu1 + u2c ≤ 2 bu1 + 3u2c , ∀u ∈ R4+.

Chapitre 5 : Méthode de plans coupants 5.8

Cas 1 : bu1 + u2c = 0

−2u1 + 2u2 ≤ 2u2 ≤ u1 + 3u2

⇒ b−2u1 + 2u2c ≤ bu1 + 3u2c ≤ 2 bu1 + 3u2c

Cas 2 : bu1 + u2c = 1 ⇒ 1 ≤ u1 + u2 < 2

Cas 2.1 : u2 < u1 ⇒ b−2u1 + 2u2c ≤ −1

b−2u1 + 2u2c+3 bu1 + u2c ≤ 2 bu1 + u2c ≤ 2 bu1 + 3u2c

Cas 2.2 : u2 ≥ u1 ⇒ 2u2 ≥ u1 + u2 ≥ 1.

De plus, bu1 + 3u2c = bu1 + u2 + 2u2c ≥ b1 + 2u2c ≥ 2.

b−2u1 + 2u2c + 3 bu1 + u2c = bu1 + 3u2 − 3u1 − u2c + 3

≤ bu1 + 3u2 − 1c + 3
= bu1 + 3u2c + 2 ≤ 2 bu1 + 3u2c

Cas 3 : bu1 + u2c ≥ 2 ⇒ u1 + u2 ≥ 2

b−2u1 + 2u2c + 3 bu1 + u2c ≤ −2u1 + 2u2 + 3u1 + 3u2

= 2(u1 + 3u2) − (u1 + u2)
≤ 2(u1 + 3u2 − 1)
≤ 2 bu1 + 3u2c


Chapitre 5 : Méthode de plans coupants 5.9

Définition: Les inégalités C-G générées à partir des in-

égalités ATx ≤ b sont des inégalités de rang 1.

Dénotons par (A2)Tx ≤ b2 le système d’inégalités com-

posé des inégalités de ATx ≤ b et de toutes les inégalités
de C-G de rang 1.

On peut répéter la procédure de C-G sur le système

(A2)Tx ≤ b2 pour trouver des inégalités de C-G de rang
2 et définir un polyèdre X 2 ⊇ conv(S). En répétant
cette procédure k fois, on obtient des inégalités de C-G
de rang k et un polyèdre X k ⊇ conv(S).

Théorème: Si X 0 est un polytope rationnel, alors il

existe un entier k tel que X k = conv(X 0 ∩ Zn).

Définition: Le plus petit entier k est appelé le rang de

Chvátal.

Étant donné une solution fractionnaire d’une relaxation

linéaire, il est impossible d’énumérer toutes les inégali-
tés de C-G pour trouver celles qui sont violées.
Chapitre 5 : Méthode de plans coupants 5.10

5.3 Algorithme de Gomory

Gomory a proposé une façon indirecte d’identifier des

coupes de C-G. L’algorithme nécessite une base opti-
male de l’algorithme du simplexe.

Considérons le PNE suivant :

(P N E) z = min cT x
x
sujet à : Ax = b
x ∈ Nn

qui inclut des variables d’écart et de surplus au besoin.

B : matrice de base et ensemble des indices des variables

de base

H : ensemble des indices des variables hors-base

āij = (B −1A)ij

b̄i = (B −1b)i

c̄j : coût réduit de xj

Chapitre 5 : Méthode de plans coupants 5.11

À l’optimalité (pour la relaxation linéaire) :

c̄j ≥ 0, ∀j ∈ B ∪ H
xi = b̄i, ∀i ∈ B
xj = 0, ∀j ∈ H

Si b̄i 6∈ N pour i ∈ B, alors on peut construire une coupe

de Gomory comme suit.

Soit les parties fractionnaires des termes de l’équation i :

fi = b̄i − bb̄ic > 0

fij = āij − bāij c, ∀j ∈ H

À l’optimalité, cette équation s’écrit :

X
xi + āij xj = b̄i
j∈H
X X
⇒ xi + bāij cxj − bb̄ic = fi − fij xj
j∈H j∈H
Chapitre 5 : Méthode de plans coupants 5.12

De plus,
X
xi + āij xj = b̄i
j∈H
X
⇒ xi + bāij cxj ≤ b̄i
j∈H
X
⇒ xi + bāij cxj ≤ bb̄ic
j∈H
X
⇒ xi + bāij cxj − bb̄ic ≤ 0
j∈H
X
⇒ fi − fij xj ≤ 0
j∈H

La coupe de Gomory est

X
fij xj ≥ fi
j∈H

Remarques :
• Puisque xj = 0, ∀j ∈ H, et fi > 0, cette coupe est
violée par la solution optimale de la relaxation linéaire
• De telles coupes peuvent aussi être générées pour toute
base non optimale
• Sous certaines hypothèses, l’algorithme de plans cou-
pants de Gomory converge en un nombre fini d’itéra-
tions
Chapitre 5 : Méthode de plans coupants 5.13

5.4 Plans coupants spécifiques

Pour un problème spécifique, on peut parfois identifier

une ou plusieurs familles d’inégalités valides pouvant
mener à des plans coupants.

Par exemple, considérons le problème de partitionne-

ment d’ensemble
X
(P P E) min cj yj
y
j∈J
X
sujet à : aij yj = 1, ∀i ∈ I
j∈J
y ∈ Bn

pour lequel il existe des inégalités de clique et des in-

égalités de cycle impair.

Une inégalité de clique se définit à partir d’un sous-

ensemble C ⊆ J des indices des colonnes qui possède la
propriété que toutes les paires de colonnes (j, k) dans C
sont en conflit, i.e., il existe au moins une rangée i ∈ I
telle que aij = aik = 1. Pour un ensemble C donné,
l’inégalité est
X
yj ≤ 1
j∈C
Chapitre 5 : Méthode de plans coupants 5.14

Une inégalité de cycle impair se définit aussi à partir

d’un sous-ensemble ordonné de cardinalité impaire H =
{h1, . . . , h`} ⊆ J des indices des colonnes qui possède la
propriété que toutes les paires de colonnes (hm, hm+1),
m = 1, . . . , ` − 1, et (h`, h1) sont en conflit. Pour un
ensemble H donné, l’inégalité est
X |H| − 1
yj ≤
j∈H
2

Remarque : Si |H| = 3, alors l’inégalité est aussi une

inégalité de clique.

Étant donné ȳ une solution fractionnaire de P P E, on

doit résoudre un problème de séparation à l’aide d’un
algorithme de séparation pour tenter de trouver une in-
égalité violée. Ce problème et cet algorithme sont spé-
cifiques à la famille d’inégalités recherchées.
Chapitre 5 : Méthode de plans coupants 5.15

Par exemple, pour les inégalités de clique, le problème

de séparation correspond à trouver le sous-ensemble C
P
de colonnes en conflit deux à deux tel que ȳj est
j∈C
maximum. Ce problème peut se formuler comme suit :
X
max ȳj sj
s
j∈J
sujet à : si + sj ≤ 1, ∀(i, j) ∈ F
s ∈ Bn

où sj vaut 1 si l’indice j fait partie de C et 0 sinon, et

F est l’ensemble des paires d’indices (i, j) telles que les
colonnes i et j ne sont pas en conflit. On peut restreindre
l’ensemble des variables aux variables telles que ȳj ∈
(0, 1).

En théorie des graphes, ce problème se formule sur un

graphe conflictuel G = (V, E)
• l’ensemble des sommets V comprend un sommet par
variable yj auquel on associe la valeur ȳj (poids)
• l’ensemble des arêtes E comprend une arête (u, v) si
les colonnes d’indices u et v sont en conflit.
Notons par GR = (VR , ER ) le graphe restreint aux som-
mets j ∈ J tels que ȳj ∈ (0, 1).
Chapitre 5 : Méthode de plans coupants 5.16

Sous cette forme, le problème de séparation consiste à

trouver une clique de poids maximal dans GR . Ce pro-
blème est NP-complet.

L’algorithme de séparation doit permettre de résoudre

le problème de séparation. Comme ce problème est NP-
complet pour les inégalités de clique, on a plutôt recours
à un algorithme heuristique semblable au suivant.

Soit C un ensemble de sommets et W (C) l’ensemble des

sommets en conflit avec tous les sommets de C.

Algorithme 5.1 : Recherche heuristique d’inégalités de

clique violées
1: Pour tout j ∈ V faire
2: Poser C = {j}
3: Tant que W (C) 6= ∅ faire
4: Choisir u ∈ arg max ȳv
v∈W (C)
5: Poser C = C ∪ {u}
P
6: Si ȳj > 1 alors
j∈C
7: C engendre une inégalité de clique violée
Chapitre 5 : Méthode de plans coupants 5.17

Une inégalité de cycle impair est violée si

X |H| − 1
ȳj >
j∈H
2
X
⇒ |H| − 2 ȳj < 1
j∈H
`−1
X
⇒ (1 − ȳm − ȳm+1) + 1 − ȳ` − ȳ1 < 1
m=1

Le problème de séparation des inégalités de cycle impair

peut aussi se formuler sur le graphe GR = (VR , ER ) en
associant des poids 1 − ȳu − ȳv aux arêtes (u, v). Le
problème consiste alors à trouver un cycle de cardinalité
impaire et de poids minimal dans GR .

Pour ce problème, il existe un algorithme de séparation

en temps polynomial. Cet algorithme peut produire un
cycle impair
• non élémentaire, i.e., passant plusieurs fois par un
même sommet (dans ce cas, le coefficient de la va-
riable associée à ce sommet dans l’inégalité est égal
au nombre de passages)
• ayant une ou plusieurs cordes (il existe m1, m2 ∈ H
tels que (m1, m2) ∈ ER ne fait pas partie du cycle)
Chapitre 5 : Méthode de plans coupants 5.18

On peut montrer que

• les inégalités de clique de cardinalité maximale défi-
nissent des facettes
• les inégalités de cycle impair pour des cycles élémen-
taires et sans corde définissent des facettes

Par conséquent, pour les inégalités de cycle impair, on

peut préférer utiliser un algorithme heuristique pour
trouver des cycles impairs élémentaires sans corde.

Les coupes trouvées peuvent souvent être renforcées (lif-

tées) en leur ajoutant des variables.

Pour les inégalités de clique, on peut ajouter dans C

des sommets se trouvant dans V \ VR en autant qu’ils
soient en conflit avec tous les autres sommets sélection-
nés. Habituellement, on ajoute un sommet à la fois dans
l’ensemble C.
Chapitre 5 : Méthode de plans coupants 5.19

Pour les inégalités de cycle impair, on peut aussi ajouter

dans C des sommets de V \VR , un à la fois. Le coefficient
d’une variable yk , k ∈ V \ VR , peut être différent de 1
et peut se trouver en résolvant le PNE
X
zk = max d i wi
w
i∈C
sujet à : wi + wj ≤ 1, ∀(i, j) ∈ E(C ∪ {k})
wk = 1
wi ∈ B, ∀i ∈ C

où E(C ∪ {k}) est l’ensemble des arêtes entre les som-
mets de C ∪{k} et di est le coefficient de i dans la coupe.
|H|−1
Le coefficient de dk est fixé à 2
− zk .
Chapitre 5 : Méthode de plans coupants 5.20

5.5 Branch-and-cut pour le problème de sac à dos

Pour le problème de sac à dos, voyons un algorithme de

branch-and-cut qui fait appel à des inégalités de couver-
ture. Ce problème se formule :

z = max cT x
x
sujet à : aTx ≤ b
x ∈ Bn

où on suppose que c ≥ 0, b ≥ a1 ≥ . . . ≥ an > 0 et tous

ces coefficients sont entiers.

Soit S = {x ∈ Bn | aTx ≤ b}.

Il est facile de montrer que dim(conv(S)) = n.

5.5.1. Inégalités de couverture

Soit C ⊆ N = {1, . . . , n}. Définissons xC comme


1 si i ∈ C
xC i =
0 sinon
Chapitre 5 : Méthode de plans coupants 5.21

Si xC 6∈ S (i.e.,
P
Définition: ai > b), alors C est
i∈C
appelé une couverture de S.

Proposition: Si C est une couverture de S, alors

X
xi ≤ |C| − 1
i∈C

est une inégalité valide pour S, appelée inégalité de cou-

verture.

P
Preuve : Soit x̄ ∈ S tel que x̄i > |C|−1. Alors x̄i = 1,
i∈C
C
∀i ∈ C. D’où a x̄ ≥ a x̄ > b. Contradiction.
T T


Définition: C ⊂ N est une couverture minimale si xC 6∈

S et xD ∈ S, ∀D ⊂ C.

Remarque : Si C = N est une couverture minimale,

P
alors xi ≤ n − 1 engendre une facette de conv(S).
i∈N
Chapitre 5 : Méthode de plans coupants 5.22

Voyons un algorithme de séparation. Soit x̂ une solu-

tion fractionnaire. Il existe une couverture C telle que
P
xi ≤ |C| − 1 est violée par x̂ si et seulement si
i∈C
X X
ai ≥ b + 1 et (1 − x̂i) < 1
i∈C i∈C

X
⇔ z= min (1 − x̂i) <1
C⊆N
i∈C
X
s.à ai ≥ b + 1
i∈C

X
⇔ z= min (1 − x̂i)wi <1
w
i∈N
s.à aTw ≥ b + 1
w ∈ Bn

où wi = 1 si i ∈ C.

Par conséquent, si z ≥ 1, alors il n’existe pas de couver-

ture C ⊆ N telle que l’inégalité est violée par x̂. Sinon
la solution optimale permet d’en identifier une.

Remarques :
• Si x̂i = 1, alors on peut fixer wi = 1.
• Si x̂i = 0, alors on peut fixer wi = 0.
Chapitre 5 : Méthode de plans coupants 5.23

Proposition: Soit C une couverture de S et E(C) =

C ∪ {i | ai ≥ aj , ∀j ∈ C}, alors
X
xi ≤ |C| − 1
i∈E(C)

est une inégalité valide pour S.

On peut faire mieux.

Proposition: Soit C = {i1, i2, . . . , ir } une couverture

minimale de S avec i1 < . . . < ir . L’inégalité
X X
αi xi + xi ≤ |C| − 1
i<i1 i∈C

est valide pour S avec




 1 si ai1 ≤ ai < ai1 + ai2
2 si ai1 + ai2 ≤ ai < ai1 + ai2 + ai3
αi = .. ...

 .
r−1

si ai1 + . . . + air−1 ≤ ai ≤ b

Preuve intuitive : Soit x̄ ∈ S. Si x̄i = 0, alors la valeur de

αi n’importe pas. Si x̄i = 1 et ai ≥ ai1 , alors ai dépasse
le volume d’au moins αi items de C. 

Une telle inégalité définit une facette de conv(S).

Chapitre 5 : Méthode de plans coupants 5.24

5.5.2. Algorithme branch-and-cut

Notation :

N A : ensemble des noeuds actifs

k : compteur de noeuds

F i : ensemble des coupes pour le noeud i

I0i : ensemble des indices des variables fixées à 0 au noeud i

I1i : ensemble des indices des variables fixées à 1 au noeud i

P (i) : noeud-père du noeud i

zIP : coût de la meilleure solution trouvée

1. k := 0, N A := {0}, zIP := −∞, I00 := I10 := ∅

2. Tant que N A 6= ∅ faire

(a) Choisir un noeud i de N A

Chapitre 5 : Méthode de plans coupants 5.25

(b) Résoudre la relaxation linéaire au noeud i :

i
zLP = max cT x
x
s.à. aTx ≤ b
coupes de F i
0 ≤ xj ≤ 1, ∀j ∈ N
xj = 0, ∀j ∈ I0i
xj = 1, ∀j ∈ I1i

pour obtenir une solution optimale x∗i (s’il y a

lieu).

i
(c) Si cette relaxation est non réalisable ou bzLP c≤
zIP , alors N A := N A \ {i}

(d) Sinon si x∗i est entière et zLP

i
> zIP , alors zIP :=
i P (j)
zLP et N A := {j ∈ N A | zLP > zIP }
Chapitre 5 : Méthode de plans coupants 5.26

(e) Sinon rechercher une inégalité de couverture vio-

lée

i. Si une telle inégalité est trouvée, alors la lifter

et l’ajouter à F i avant de retourner en 2.b

ii. Sinon choisir une variable fractionnaire xj

• N A := N A ∪ {k + 1, k + 2} \ {i}
• I0k+1 := I0i ∪ {j}, I1k+1 := I1i
• I1k+2 := I1i ∪ {j}, I0k+2 := I0i
• F k+1 := F i, F k+2 := F i
• P (k + 1) := i, P (k + 2) := i
• k := k + 2