Coupes de Chvtal-Gomory a
Pierre Bonami
Optimisation Combinatoire, Masters II, ID et IF
17 dcembre 2012 e
Premi`re partie I e Rappels
Plans coupants
Soit X = {Ax b, x 0, xj Z, j = 1, . . . , p}. Comme x minimize la relaxation continue et x X , on a x conv(X ) (x est une solution de base de (PL)). Th. de Separation si P est convexe et x P, hyperplan T x = tel que T x x P et T x .
1 x = (6, 2 )
Plans coupants
Soit X = {Ax b, x 0, xj Z, j = 1, . . . , p}. Comme x minimize la relaxation continue et x X , on a x conv(X ) (x est une solution de base de (PL)). Th. de Separation si P est convexe et x P, hyperplan T x = tel que T x x P et T x .
1 x = (6, 2 )
` 1. Probleme de separation : Trouver T x = sparant X e et x . 2. Ajouter T x ` (PL) et rpter les tapes (re-rsoudre a e e e e PL, vrier 1. et 2.,...). e
Plans coupants
Soit X = {Ax b, x 0, xj Z, j = 1, . . . , p}. Comme x minimize la relaxation continue et x X , on a x conv(X ) (x est une solution de base de (PL)). Th. de Separation si P est convexe et x P, hyperplan T x = tel que T x x P et T x .
1 x = (6, 2 )
` 1. Probleme de separation : Trouver T x = sparant X e et x . 2. Ajouter T x ` (PL) et rpter les tapes (re-rsoudre a e e e e PL, vrier 1. et 2.,...). e
Deuxi`me partie II e
Quelques rsultats sur les syst`me dingalits l e e e e
Elimination de Fourrier Motzkin
Soit P := {x : Ax b} (n variables, m contraintes).
Question Comment dterminer si P = . e
Elimination de Fourrier Motzkin
Soit P := {x : Ax b} (n variables, m contraintes).
Question Comment dterminer si P = . e Approche de Fourrier : Eliminer une par une les variable de P jusqu` : a
Elimination de Fourrier Motzkin
Soit P := {x : Ax b} (n variables, m contraintes).
Question Comment dterminer si P = . e Approche de Fourrier : Eliminer une par une les variable de P jusqu` : a
1. Une contradiction ( P = ), ou
Elimination de Fourrier Motzkin
Soit P := {x : Ax b} (n variables, m contraintes).
Question Comment dterminer si P = . e Approche de Fourrier : Eliminer une par une les variable de P jusqu` : a
1. Une contradiction ( P = ), ou 2. Un interval en dimension 1.
Elimination de Fourrier Motzkin
Soit P := {x : Ax b} (n variables, m contraintes).
Question Comment dterminer si P = . e Approche de Fourrier : Eliminer une par une les variable de P jusqu` : a
1. Une contradiction ( P = ), ou 2. Un interval en dimension 1.
P scrit : e
a11 x1 + . . . . . . aj1 x1 + . . . . . .
+a1n xn b1
+ajn xn bj
am1 x1 + . . . +amn xn bm
Etape dlimination e
On limine la derni`re variable xn . Soient : e e
I + := {i {1, . . . , m} : ain > 0 I := {i {1, . . . , m} : ain < 0 I 0 := {i {1, . . . , m} : ain = 0 ai1 x1 + . . . +ai(n1) xn1 + ain xn bi ai1 x1 + . . . +ai(n1) xn1 + ain xn bi ai1 x1 + . . . +ai(n1) xn1 bi i I+ i I i I0
e P scrit :
Etape dlimination e
On limine la derni`re variable xn . Soient : e e + := {i {1, . . . , m} : a > 0 I in := {i {1, . . . , m} : a < 0 I in 0 := {i {1, . . . , m} : a = 0 I in P se re-crit : e ai(n1) ai1 bi x1 + . . . + xn1 + xn ain ain ain ai(n1) ai1 bi x1 + . . . + xn1 xn ain ain ain ai1 x1 + . . . +ai(n1) xn1 bi i I+ i I i I0
Etape dlimination e
On limine la derni`re variable xn . Soient : e e + := {i {1, . . . , m} : a > 0 I in := {i {1, . . . , m} : a < 0 I in 0 := {i {1, . . . , m} : a = 0 I in P se re-crit : e ai(n1) ai1 bi x1 + . . . + xn1 + xn ain ain ain ai(n1) ai1 bi x1 + . . . + xn1 xn ain ain ain ai1 x1 + . . . +ai(n1) xn1 bi Pour tout i + I + et i I on a :
n1 j=1
i I+ i I i I0
ai j bi b+ xj xn i ai n ai n ai + n
n1 j=1
ai + j xj ai + n
Etape dlimination e
On limine la derni`re variable xn . Soient : e e
I + := {i {1, . . . , m} : ain > 0 I := {i {1, . . . , m} : ain < 0 I 0 := {i {1, . . . , m} : ain = 0
On peut maintenant liminer xn , on obtient P : e a ai + 1 i 1 ai + n ai n + x1 + . . . xn1 bi+ b i ai + n ai n bi i + I + , i I i I 0
ai(n1) ai 1 ain ai (n1)
ai1 x1 + . . . + ai(n1) xn1
Thor`me e e
(x1 , . . . , xn1 ) P xn tel que (x1 , . . . , xn ) P
Lemme de Farkas
Question :
Sous quelle conditions P est vide ?
Lemme de Farkas
Question :
Sous quelle conditions P est vide ?
Thor`me e e
Le syst`me P := {x : Ax b} na pas de solutions si et seulement e si le syst`me uA = 0, ub < 0 et u 0 a une solution. e
Lemme de Farkas
Question :
Sous quelle conditions P est vide ?
Thor`me e e
Le syst`me P := {x : Ax b} na pas de solutions si et seulement e si le syst`me uA = 0, ub < 0 et u 0 a une solution. e
Dmonstration. e
Supposons x P, pour tout u 0, uAx ub. Si u 0 tel que uA = 0 et ub < 0, x : uAx = 0 > ub donc x P. Pour le sens inverse, on suppose P = , en appliquant llimination e de Fourrier on trouve u satisfaisant le thor`me. e e
Corollaires du Lemme de Farkas
Corrolaire
Le syst`me Ax b a une solution si et seulement si u 0 tel que e uA = 0 on a ub 0.
Corollaires du Lemme de Farkas
Corrolaire
Le syst`me Ax b a une solution si et seulement si u 0 tel que e uA = 0 on a ub 0.
Corrolaire (Programmation linaire) e
Le syst`me Ax = b, x 0 a une solution si et seulement si u tel e que uA 0 on a ub 0.
Corollaires du Lemme de Farkas
Corrolaire
Le syst`me Ax b a une solution si et seulement si u 0 tel que e uA = 0 on a ub 0.
Corrolaire (Programmation linaire) e
Le syst`me Ax = b, x 0 a une solution si et seulement si u tel e que uA 0 on a ub 0.
Corrolaire
Le syst`me Ax + By f Cx + Dy = g , x 0 a une solution si et e seulement si (u, v ) tel que uA + vC 0, uB + vD = 0 et u 0 on a uf + vg 0.
Dualit forte en Programmation Linaire e e
Thor`me e e
Soient P := {x : Ax b} et D := {u : uA = c, u 0}. (a) Si P = et D = : max{cx : x P} = min{ub : u D}.
(b) Si P = et D = , max{cx : x P} nest pas born. e
Dualit forte en Programmation Linaire e e
Thor`me e e
Soient P := {x : Ax b} et D := {u : uA = c, u 0}. (a) Si P = et D = : max{cx : x P} = min{ub : u D}.
(b) Si P = et D = , max{cx : x P} nest pas born. e
Ide de preuve. e
Cas (a). xinP et u D on a cx = uAx ub (dualit faible). e En utilisant (plusieurs fois) le lemme de Farkas on montre que si P = et D = , le syst`me : e Ax b, uA = c, u 0, ub cx est ralisable. e
Ingalit valides pour une Programme Linaire e e e
Denition
x est une ingalit valide pour P R n si x P, x . e e
Ingalit valides pour une Programme Linaire e e e
Denition
x est une ingalit valide pour P R n si x P, x . e e Question : Si P := {x : Ax b}, ` quelle condition x est a une ingalit valide pour P ? e e
Ingalit valides pour une Programme Linaire e e e
Denition
x est une ingalit valide pour P R n si x P, x . e e Question : Si P := {x : Ax b}, ` quelle condition x est a une ingalit valide pour P ? e e
Thor`me e e
Supposons P = . x est valide pour P si et seulement si u 0 tel que = uA et ub.
Ingalit valides pour une Programme Linaire e e e
Denition
x est une ingalit valide pour P R n si x P, x . e e Question : Si P := {x : Ax b}, ` quelle condition x est a une ingalit valide pour P ? e e
Thor`me e e
Supposons P = . x est valide pour P si et seulement si u 0 tel que = uA et ub.
Dmonstration. e
Si u 0 tel que = uA et ub, x P : x = uAx ub . Si x est valide, max{x : x P} . Par la dualit e max{x : x P} = min{ub : uA = , u 0}, la solution optimale u satisfait le Thor`me. e e
Troisi`me partie III e Coupes de Chvtal-Gomory a
Rappels : Algorithme de plans coupants
On consid`re un programme en nombres entiers pur : e max cx Ax b x 0 x Zn
Algorithme
1. C 2. Rsoudre la relaxation continue e max{cx : Ax b, x , , C, x 0}. Soit x la solution. 3. Si x Zn FIN. 4. Trouver x tel que > et x pour tout x Zn x tel que Ax b et x 0. 5. Ajouter , ` C et aller en 2. a
Un principe de coupe
Un principe simple
Si x Z et x f f Z alors x f o` f est la partie enti`re u e de f .
Utilisation
Soit une ingalit x telle que i Z i = 1, . . . , n. Si x e e satisfait lingalit et x est entier x . e e
Exemple
x Z2 tel que x1 + x2 1.9
Un principe de coupe
Un principe simple
Si x Z et x f f Z alors x f o` f est la partie enti`re u e de f .
Utilisation
Soit une ingalit x telle que i Z i = 1, . . . , n. Si x e e satisfait lingalit et x est entier x . e e
Exemple
x Z2 tel que x1 + x2 1.9
Un principe de coupe
Un principe simple
Si x Z et x f f Z alors x f o` f est la partie enti`re u e de f .
Utilisation
Soit une ingalit x telle que i Z i = 1, . . . , n. Si x e e satisfait lingalit et x est entier x . e e
Exemple
x Z2 tel que x1 + x2 1.9 x1 + x2 1.9 = 1
Coupes de Chvtal-Gomory a
Thor`me e e
Si x Zn vrie Ax b, lingalit uAx ub est valide pour e e e m. tout u 0 tel que uA Z
Exemple
On consid`re le polyh`dre donn par les ingalits : e e e e e x1 + x2 2 3x1 + x2 5
Coupes de Chvtal-Gomory a
Thor`me e e
Si x Zn vrie Ax b, lingalit uAx ub est valide pour e e e m. tout u 0 tel que uA Z
Exemple
On consid`re le polyh`dre donn par les ingalits : e e e e e x1 + x2 2 3x1 + x2 5
Coupes de Chvtal-Gomory a
Thor`me e e
Si x Zn vrie Ax b, lingalit uAx ub est valide pour e e e m. tout u 0 tel que uA Z
Exemple
On consid`re le polyh`dre donn par les ingalits : e e e e e x1 + x2 2 3x1 + x2 5 En prenant u1 = u2 = 1/2 : 2x1 + x2 3.5
Coupes de Chvtal-Gomory a
Thor`me e e
Si x Zn vrie Ax b, lingalit uAx ub est valide pour e e e m. tout u 0 tel que uA Z
Exemple
On consid`re le polyh`dre donn par les ingalits : e e e e e x1 + x2 2 3x1 + x2 5 En prenant u1 = u2 = 1/2 : 2x1 + x2 3.5 En arrondissant on obtient : 2x1 + x2 3
Fermeture lmentaire ee
Dnition e
Soient P := {x Rn : Ax b} et X = P Zn , on appelle fermeture lmentaire de Chvtal lensemble : ee a P (1) (P) = {x Rn : uAx ub, pout tout u 0 tel que uA Zn }.
Proposition
X P (1) (P) P
Application rcursive e
On peut appliquer rcursivement la procdure : e e P (2) (P) = P (1) P (1) (P) . . . P (k) (P) = P P (k1) (P)
Thor`me de Chvtal-Gomory e e a
Thor`me e e
Soit A une matrice ` coecients rationnelles et b un vecteur ` a a coecients rationelles. Toute ingalit valide pour X peut tre e e e obtenue par un nombre ni dapplication de la procdure de e Chvtal. a (i.e. conv(X ) = P k (X ) pour k ni).
Exemple
max 9x1 + 5x2 x1 6 3x1 + 2x2 19 x Z2 + u1 u3 x1 + 3x2 1 u2
Thor`me de Chvtal-Gomory e e a
Thor`me e e
Soit A une matrice ` coecients rationnelles et b un vecteur ` a a coecients rationelles. Toute ingalit valide pour X peut tre e e e obtenue par un nombre ni dapplication de la procdure de e Chvtal. a (i.e. conv(X ) = P k (X ) pour k ni).
Exemple
max 9x1 + 5x2 x1 6 3x1 + 2x2 19 x Z2 + u1 u3 x1 + 3x2 1 u2
Thor`me de Chvtal-Gomory e e a
Thor`me e e
Soit A une matrice ` coecients rationnelles et b un vecteur ` a a coecients rationelles. Toute ingalit valide pour X peut tre e e e obtenue par un nombre ni dapplication de la procdure de e Chvtal. a (i.e. conv(X ) = P k (X ) pour k ni).
Exemple
max 9x1 + 5x2 x1 6 3x1 + 2x2 19 x Z2 + u1 u3 x1 + 3x2 1 u2
u1 = 0, u2 = 3/11, u3 = 1/11
Thor`me de Chvtal-Gomory e e a
Thor`me e e
Soit A une matrice ` coecients rationnelles et b un vecteur ` a a coecients rationelles. Toute ingalit valide pour X peut tre e e e obtenue par un nombre ni dapplication de la procdure de e Chvtal. a (i.e. conv(X ) = P k (X ) pour k ni).
Exemple
max 9x1 + 5x2 x1 6 3x1 + 2x2 19 x Z2 + u1 u3 x1 + 3x2 1 u2
u1 = 0, u2 = 3/11, u3 = 1/11 x1 1 (u4 )
Thor`me de Chvtal-Gomory e e a
Thor`me e e
Soit A une matrice ` coecients rationnelles et b un vecteur ` a a coecients rationelles. Toute ingalit valide pour X peut tre e e e obtenue par un nombre ni dapplication de la procdure de e Chvtal. a (i.e. conv(X ) = P k (X ) pour k ni).
Exemple
max 9x1 + 5x2 x1 6 3x1 + 2x2 19 x Z2 + u1 u3 x1 + 3x2 1 u2
u1 = 0, u2 = 3/11, u3 = 1/11 x1 1 (u4 )
Thor`me de Chvtal-Gomory e e a
Thor`me e e
Soit A une matrice ` coecients rationnelles et b un vecteur ` a a coecients rationelles. Toute ingalit valide pour X peut tre e e e obtenue par un nombre ni dapplication de la procdure de e Chvtal. a (i.e. conv(X ) = P k (X ) pour k ni).
Exemple
max 9x1 + 5x2 x1 6 3x1 + 2x2 19 x Z2 + u1 u3 x1 + 3x2 1 u2
u1 = 0, u2 = 3/11, u3 = 1/11 x1 1 (u4 )
Retour aux plans coupants
Algorithme
1. C 2. Rsoudre la relaxation continue e max{cx : Ax b, x , , C, x 0}. Soit x la solution. 3. Si x Zn FIN. 4. Trouver x tel que > et x pour tout x Zn x tel que Ax b et x 0. 5. Ajouter , ` C et aller en 2. a a On suppose A ` coecients entiers.
Rsolution de la relaxation continue e
Le programme linaire est mis sous forme standard (par lajout de e variables dcarts) : e max cx A x = b x 0 x Zn+m et rsolu par la mthode du simplexe. e e A loptimum de la relaxation continue, on a une base B et un tableau du simplexe : xB + B 1 NxN = B 1 b o` N est la matrice des variables hors base, et la solution optimale x est u donne par xN = 0 et xB = B 1 b. On note A = B 1 A et a0 = B 1 b. e Une ligne du tableau est de la forme : xi +
jB
aij xj = ai0
Si a0 Zm la solution optimale de la relaxation continue est enti`re e (FIN). Sinon, il existe i tel que ai0 Z
Sparation dune coupe de Gomory e
xi +
jB
aij xj = ai0
On note fj = aij aij xi +
jB
fj xj +
jB
aij xj = ai0
Comme xj 0 et fj 0, cette galit implique ; e e xi +
jB
aij xj ai0
Le membre de gauche est entier, on peut arrondir celui de droite : xi +
jB
aij xj ai0
Sparation dune coupe de Gomory (II) e
Lingalit e e xi +
jB
aij xj ai0
nest pas satisfaite par la solution courante : xi = ai0 et xj = 0 pour j B donc : xi +
jB
aij j = ai0 > ai0 x
On peut donc ajouter cette ingalit et appliquer lalgorithme de e e sparation. e
Algorithme de Gomory
On suppose A ` coecients entiers. a 1. C 2. Rsoudre la relaxation continue e max{cx : Ax b, x , , C, x 0}, par lalgorithme du simplexe. Soit x la solution et B la base optimale. 3. Si x Zn FIN. 4. Choisir une ligne du tableau : xi +
jB
aij xj = ai0
telle que ai0 Z. 5. Ajouter lingalit de Gomory e e xi +
jB
aij xj ai0
et aller en 2.
Finitude de lalgorithme
Solution lexicographiquement minimale
Une solution x est dite lexicographiquement optimale si :
elle est optimale ; elle est minimale dans lordre lexicographique : toute autre solution optimale x est telle que x1 < x 1 ou (1 = x 1 et x2 < x 2 ) ou . . . x
ou (i = x i pour i = 1,. . . ,n-1 et xn < x n ) x
Thor`me de Gomory e e
Lalgorithme converge en temps ni si la relaxation continue est rsolue ` une solution lexicographiquement optimale ` chaque e a a itration. e
Remarques
Lalgorithme de Gomory a t dcouvert en 1958. ee e
Remarques
Lalgorithme de Gomory a t dcouvert en 1958. ee e Tr`s vite (1960 ?) il a t considr comme inutile en e ee ee pratique : mauvaise convergence, numriquement instable. . . e
Remarques
Lalgorithme de Gomory a t dcouvert en 1958. ee e Tr`s vite (1960 ?) il a t considr comme inutile en e ee ee pratique : mauvaise convergence, numriquement instable. . . e En 2008 Zanette, Balas et Fischetti ont (re)dcouvert que e lalgorithme original de Gomory ne marchait pas si mal. En 2010, Z.B.F. donnent comme exemple un probl`me pos e e par Knuth en 1960 avec 51 variables et 43 contraintes rsolu e pour la premi`re fois en 1995 avec CPLEX. e
Par branch-and-cut, le probl`me est rsolu en 6 secondes et e e 91 000 nuds. Lalgorithme de Gomory (lg`rement modi) rsoud le e e e e probl`me en 0,15 secondes avec 1 032 coupes ! e
Importance de lordre lexicographique
Gomory pensait que lordre lexicographique tait une e technicit thorique uniquement ncessaire pour la preuve. e e e En fait, il joue un ordre capital en pratique.
Figure: Nombre ditration de lalgorithme avec dirente options. e e
Quatri`me partie IV e Coupes de Gomory Mixtes
Coupes mixtes de Gomory
Les coupes de Gomory peuvent uniquement tre utilises pour un e e probl`me en nombres entiers pur. e Nous considrons maintenant un probl`me mixte : e e max cx Ax b x 0 xi Z i I {1, . . . , n}
Principe disjonctif
Un principe simple
Si x Rn , x 0 et x satisfait soit la contrainte i=1 ai1 xi 1 soit la n contrainte i=1 ai2 xi 1. Alors x satisfait la contrainte :
n n
max{ai1 , ai2 }xi 1
i=1
Exemple
Si x 0 satisfait soit x2 x1 + 1 2 2 soit 3 x2 x1 + 1 5 5
Principe disjonctif
Un principe simple
Si x Rn , x 0 et x satisfait soit la contrainte i=1 ai1 xi 1 soit la n contrainte i=1 ai2 xi 1. Alors x satisfait la contrainte :
n n
max{ai1 , ai2 }xi 1
i=1
Exemple
Si x 0 satisfait soit x2 x1 + 1 2 2 soit 3 x2 x1 + 1 5 5
Principe disjonctif
Un principe simple
Si x Rn , x 0 et x satisfait soit la contrainte i=1 ai1 xi 1 soit la n contrainte i=1 ai2 xi 1. Alors x satisfait la contrainte :
n n
max{ai1 , ai2 }xi 1
i=1
Exemple
Si x 0 satisfait soit x2 x1 + 1 2 2 soit 3 x2 x1 + 1 5 5
Principe disjonctif
Un principe simple
Si x Rn , x 0 et x satisfait soit la contrainte i=1 ai1 xi 1 soit la n contrainte i=1 ai2 xi 1. Alors x satisfait la contrainte :
n n
max{ai1 , ai2 }xi 1
i=1
Exemple
Si x 0 satisfait soit x2 x1 + 1 2 2 soit 3 x2 x1 + 1 5 5
Principe disjonctif
Un principe simple
Si x Rn , x 0 et x satisfait soit la contrainte i=1 ai1 xi 1 soit la n contrainte i=1 ai2 xi 1. Alors x satisfait la contrainte :
n n
max{ai1 , ai2 }xi 1
i=1
Exemple
Si x 0 satisfait soit x2 x1 + 1 2 2 soit 3 x2 x1 + 1 5 5 il satisfait : 3 x2 x1 + 1 5 2
Drivation dune coupe mixte simple e
On consid`re toujours une ligne du tableau (maintenant certaines e variables sont continues) corrspondant a une variable de base enti`re e (xi Z) : xi + aij xj = ai0
jB
Soit f0 = ai0 ai0 . On recrit la ligne : e aij xj f0 = ai0 xi
jB
Comme ai0 xi Z on a soit ai0 xi 0 soit ai0 xi 1 et donc soit aij xj f0 0
jB
soit aij xj f0 1.
jB
Drivation dune coupe mixte simple (II) e
En rarangeant les termes, soit e aij xj f0
jB
soit aij xj f0 1.
jB
On divise la premi`re ingalit par f0 > 0 et la seconde par f0 1 < 0, soit e e e aij x 1 f0 j
jB
soit
jB
aij x 1. f0 1 j
On peut maintenant appliquer le principe disjonctif, on obtient : max{
jB
aij aij , }x 1. f0 f0 1 j
Remarque
Comme f0 > 0 et f0 1 < 0 : max{ et lingalit scrit : e e e aij x + f0 j aij x 1. 1 f0 j aij aij , }= f0 f0 1
aij f0 aij f0 1
si aij > 0 si aij < 0.
jB,aij >0
jB,aij <0
Une meilleure ingalit : Ingalit Mixte de Gomory e e e e
Au dbut de la drivation on peut amliorer l egalit en direnciant les e e e n e e variables hors bases enti`res et continues dans la ligne du tableau : e xi +
jB,jI
aij xj +
jB,jI
aij xj = ai0
Soit f0 = ai0 ai0 , fj = aij aij . La ligne peut se recrire : e xi +
jB,jI ,fj f0
fj xj +
jB,jI ,fj >f0
(1 fj )xj
jB,jI
aij xj = aij xj
jB,jI ,fj >f0
ai0 xi
jB,jI ,fj f0
aij xj
(1)
En utilisant lintgrit du membre de droite on peut driver une coupe de e e e la mme mani`re, on obtient : e e fj x+ f0 j 1 fj x+ 1 f0 j aij x+ f0 j aij x 1. 1 f0 j
jB,jI ,fj f0
jB,jI ,fj >f0
jB,jI ,aij >0
jB,jI ,aij <0
Comparaison des coupes de Gomory pures et Mixtes
Si on suppose le probl`me entier, on peut montrer que lingalit mixte e e e fj x + f0 j 1 fj x 1. 1 f0 j
jB,fj f0
jB,fj >f0
domine lingalit pure : e e xi +
jB
aij xj ai0 .
Remarques
Pour les programmes mixtes, lalgorithme de Gomory ne converge pas en temps ni. En 1996, il a t dcouvert que lalgorithme pouvait en fait tre utile ee e e dans le cadre dun branch-and-cut.
Algorithme de renforcement
e 1. Rsoudre la relaxation continue max{cx : Ax b, x , , C, x 0}. Soit x la solution et B la base optimale. 2. Si x Zn FIN. 3. Pour toute les lignes du du tableau : xi +
jB
aij xj = ai0
telles que ai0 Z, ajouter lingalit Mixte de Gomory et aller en 2. e e Ces coupes sont intgres dans tous les solveurs modernes (CPLEX, e e GUROBI, GLPK, COIN-OR,. . . ).
