Considrons le programme mathmatique suivant :

max 6x1 2x2 + 10x3 + 4x4 (1) 8x1 + 3x2 + 12x3 + 8x4 20 (2) 14x1 + 10x2 + 6x3 + 16x4 25 (3) x1, x2, x3, x4 {0, 1} (4)

1. Modlisation a. Dterminer plusieurs coupes partir des contraintes (2), (3) et (4). b. Modliser (sparment) les conditions suivantes : i. Si x1 et x2 sont gaux 0, alors x3 est gal 1. ii. Si x1 ou x2 est gal 0, alors x3 est gal 0. iii. Si x1 ou x2 est gal 1, alors x3 ou x4 est gal 0.

2. Relaxation Lagrangienne a. crivez le dual Lagrangien si la contrainte (2) est relche. b. Proposez un algorithme pour rsoudre le problme relch pour une valeur quelconque du multiplicateur Lagrangien.

3. Dcrivez les principes gnraux de la gnration de colonnes.