MTH6404 Programmation en nombres entiers

Examen final - Vendredi 20 avril 2012

1. Considérons le programme en nombres entiers (PNE) suivant :

min x1 + 2x2
x
s.à. x1 + x2 ≥ 3
−x1 + 3x2 ≥ 0
5x1 + x2 ≥ 5
x1 , x2 ≥ 0, entiers.

En résolvant la relaxation linéaire de PNE par l’algorithme du simplexe, on obtient le

tableau optimal suivant :
base x1 x2 s1 s2 s3 val
−z 0 0 5/4 1/4 0 -15/4
x1 1 0 -3/4 1/4 0 9/4
x2 0 1 -1/4 -1/4 0 3/4
s3 0 0 -4 1 1 7
où s1 , s2 et s3 sont des variables de surplus associées aux contraintes. Par exemple, dans
ce tableau, la ligne débutant par x1 indique que cette variable est en base et procure
une équation x1 − 3/4s1 + 1/4s2 = 9/4 qui met cette variable en relation avec les deux
variables hors-base s1 et s2 .
(2 pts) (a) Déterminer la coupe de Gomory découlant de la première contrainte.
(2 pts) (b) Réécrire cette coupe en fonction des variables x1 et x2 .
(2 pts) (c) Est-ce que cette coupe engendre une facette de l’enveloppe convexe du domaine
réalisable de PNE ?
(2 pts) (d) S’agit-il d’une coupe de Chvátal-Gomory de rang 1 ? Spécifier d’abord le système
d’équations à résoudre pour déterminer si c’en est une.

2. Considérons P l’enveloppe convexe du domaine suivant :

{x ∈ N5 | 9x1 + 4x2 + 3x3 + 6x4 + 2x5 ≤ 9, x2 + x5 ≤ 1, x2 − x3 ≤ 0}.

(1 pt) (a) Déterminer la dimension de P .

(b) Pour chacune des inégalités valides pour P suivantes, indiquer si elle définit une
facette de P .
(2 pts) i. x4 ≥ 0.
(2 pts) ii. x4 ≤ 1.
 MTH6404 Programmation en nombres entiers - Final Hiver 2012 2

3. Considérons le programme en nombres entiers (PNE) suivant :

min c> x
x
s.à. Ax ≥ 1
x ∈ {0, 1}n

où x est le vecteur des n variables de décision, A = (aij ) est une matrice m × n ayant
seulement des éléments égaux à 0 ou 1, et 1 est un vecteur de m éléments égaux à 1. Suppo-
sons que chaque colonne de A contient au plus deux éléments non nuls, i.e., m
P
i=1 aij ≤ 2,
∀j ∈ {1, . . . , n}. Dénotons par S le domaine réalisable de PNE.
(a) Supposons que  
1 0 1 1 0 0 0 0 0 1

 1 1 0 0 0 0 1 1 0 0 

 0 1 1 0 0 0 0 0 1 0 
A= 

 0 0 0 1 0 1 0 0 0 0 

 0 0 0 0 1 0 0 1 0 0 
0 0 0 0 0 1 0 0 1 0
et qu’en résolvant la relaxation linéaire de PNE, on obtient la solution optimale
x∗LP = (0.5, 0.5, 0.5, 0, 1, 1, 0, 0, 0, 0)> .
(1 pt) i. Est-ce que A est totalement unimodulaire ?
(1 pt) ii. Est-ce que x1 + x2 + x3 ≥ 2 est une inégalité valide pour S qui permet de couper
x∗LP ?
(b) Revenons à une matrice A quelconque qui satisfait les conditions énoncées ci-haut
(au plus deux éléments égaux à 1 par colonne). Soit I ⊆ {1, . . . , m} un sous-ensemble
de cardinalité impaire des (indices des) contraintes et JI l’ensemble des (indices des)
colonnes de A qui contiennent au moins un élément non nul dans les contraintes
P
de I, i.e., JI = {j | i∈I aij ≥ 1}.
(2 pts) i. Montrer que  
X |I|
xj ≥ (1)
j∈JI
2

est une inégalité valide pour S.

(3 pts) ii. Dans une méthode de plans coupants, la recherche d’inégalités (1) violées par une
solution x∗LP de la relaxation linéaire de PNE peut se faire en résolvant un pro-
blème de séparation. Formuler ce problème de séparation comme un programme
en nombres entiers.
 MTH6404 Programmation en nombres entiers - Final Hiver 2012 3

4. Considérons un problème de transport maritime impliquant un seul produit et un horizon

de planification de T jours. Ce produit est disponible en quantité illimitée à un seul port,
le port de cueillette, et doit être distribué à un ensemble de clients I (les ports de livraison)
à l’aide d’une flotte hétérogène de bateaux B. Un bateau b ∈ B a une capacité qb . Pour
effectuer les livraisons, les bateaux font des voyages. Un voyage est un aller-retour entre le
port de cueillette et un port de livraison i ∈ I. Pour le bateau b ∈ B, un voyage au port i
nécessite tbi jours (incluant le temps de chargement et de déchargement) et coûte cbi .
Chaque livraison est une pleine cargaison, i.e., le bateau b livre toujours la quantité qb .
À chaque client i ∈ I est associée une demande di que l’on vise à satisfaire au cours
de l’horizon. Une pénalité p− +
i (resp. pi ) est encourue pour chaque unité du produit non
livrée (resp. livrée en surplus) au client i. Le problème consiste à déterminer le nombre
de voyages que chaque bateau doit effectuer à chaque client durant l’horizon de façon à
minimiser la somme des coûts de voyage et des pénalités encourues. La durée totale des
voyages effectués par chaque bateau ne doit pas excéder T , la durée de l’horizon.
Ce problème se formule comme un programme en nombres entiers qui fait appel aux
variables suivantes :
xbi : nombre de voyages du bateau b au client i ;
e−
i : quantité manquante pour atteindre la demande du client i ;

e+
i : quantité livrée en surplus au client i.

La formulation est :
XX X
min
− +
cbi xbi + (p− − + +
i ei + p i ei ) (2)
x,e ,e
b∈B i∈I i∈I
X
sujet à : tbi xbi ≤ T, ∀b ∈ B (3)
i∈I
X
qb xbi + e− +
i − ei = di , ∀i ∈ I (4)
b∈B

e− +
i , ei ≥ 0, ∀i ∈ I (5)

0 ≤ xbi ≤ ubi , entier, ∀b ∈ B, i ∈ I. (6)

Dans ce modèle, les contraintes (3) limitent le nombre total de jours de voyage pour
chaque bateau tandis que les contraintes (4) permettent de calculer le manque à livrer
(e− +
i ) ou le surplus livré (ei ) pour chaque client i. Les contraintes (5) et (6) définissent le
domaine des variables, incluant des bornes supérieures ubi sur le nombre de voyages que
chaque bateau peut effectuer à chaque client. Ces bornes supérieures se déduisent à partir
des autres données du problème.

(2 pts) (a) Déterminer les meilleures valeurs possibles pour les bornes supérieures ubi .
 MTH6404 Programmation en nombres entiers - Final Hiver 2012 4

(b) Pour calculer une borne inférieure sur la valeur optimale du modèle (2)–(6), une
méthode de relaxation lagrangienne peut être employée.
(1 pt) i. Écrire le sous-problème lagrangien obtenu en relaxant les contraintes (4).
(2 pts) ii. Quelle est la nature de ce sous-problème ? Est-il séparable ?
(c) Pour résoudre ce problème, on peut utiliser une méthode de type branch-and-price
découlant de l’application du principe de décomposition de Dantzig-Wolfe au mo-
dèle (2)–(6). Supposons que le domaine du sous-problème est défini par les contraintes (4)–
(6). Dans ce cas, on obtient un sous-problème par client.
(1 pt) i. Indiquer à quoi correspond un point extrême du domaine du sous-problème
associé au client i.
(2.5 pts) ii. Donner (directement) la formulation de la relaxation linéaire du problème maître.
Bien définir la notation employée.
(1.5 pt) iii. Formuler le sous-problème associé au client i.
(2 pts) iv. Proposer deux types de décisions de branchement qui pourraient être utilisés.
Comment imposeriez-vous ces décisions dans la méthode branch-and-price ?
(d) En considérant les variables xbi comme les variables liantes, on peut aussi appliquer la
décomposition de Benders au modèle (2)–(6). Dans ce cas, le problème maître relaxé
(PMR) à la première itération (i.e., en omettant toutes les coupes de Benders) est :
XX X
min cbi xbi + zi (7)
x,z
b∈B i∈I i∈I
X
sujet à : tbi xbi ≤ T, ∀b ∈ B (8)
i∈I

zi ≥ 0, ∀i ∈ I (9)

0 ≤ xbi ≤ ubi , entier, ∀b ∈ B, i ∈ I (10)

et il y a un sous-problème par client i qui se formule :

min
− +
p− − + +
i ei + pi ei (11)
ei ,ei
X
sujet à : e− +
i − ei = di − qb x̄bi , (12)
b∈B

e− +
i , ei ≥ 0, (13)

où x̄bi , b ∈ B, correspond à une solution du PMR.

(1 pt) i. Existe-t-il des coupes de Benders de faisabilité pour ce problème ?
(2 pts) ii. À la première itération de l’algorithme de Benders, la solution du PMR est :
xbi = zi = 0, ∀b ∈ B, i ∈ I. Quelles coupes de Benders (précisément) seraient
générées à cette itération ?

(35 pts)