Entrepôts, bin-packing et sac-à-dos

CERMICS, A. Parmentier
ENPC 12 décembre 2018
Miniprojet

Bilan sur
I séances en petite classe
I séance en autonomie

Prochaines séances en amphi

I 1h30 cours
I 1h intervenant industriel

Prochaine séance en autonomie : 16 janvier

I sur l’ordonnancement
I sous forme d’exercices de révision
I sujet une semaine avant pour que vous puissiez le travailler
I venez poser des questions

A. Parmentier, ENPC 12 décembre 2018 2 / 43

Sommaire de la partie

1. Sac à dos

2. Bin Packing

3. Positionnement d’entrepôts

4. Exercices

A. Parmentier, ENPC 12 décembre 2018 3 / 43

PROBLÈME DU SAC-À-DOS
Données. Entiers positifs ou nuls n, w1 , . . . , wn et W , et des réels
positifs ou nuls c1 , . . . , cn .
Tâche. Trouver unPsous-ensemble S ⊆ {1, . . . , n} tel que
P
j∈S wj ≤ W et j∈S cj est maximum.

A. Parmentier, ENPC 12 décembre 2018 4 / 43

Applications (et généralisations en plusieurs dimensions)

1. Gestion de portefeuilles / investissements

2. Génération de clefs en cryptographie
3. Choix de questions à traiter dans un exam noté sur plus de 20.
4. Technologie embarquée.
5. Etc.

A. Parmentier, ENPC 12 décembre 2018 5 / 43

Complexité

Théorème
Le problème du sac-à-dos est NP-difficile.

A. Parmentier, ENPC 12 décembre 2018 6 / 43

Programmation dynamique

Quelle fonction valeur pourrait être utilisée pour une approche par
programmation dynamique ?

A. Parmentier, ENPC 12 décembre 2018 7 / 43

Programmation dynamique

x(j, W 0 ) = valeur maximale d’un sac de capacité W 0 , en se limitant aux

j premiers objets.
Equation (programmation dynamique)

x(j, W 0 ) = max(x(j − 1, W 0 ), x(j − 1, W 0 − wj ) + cj ).

Complexité : O(nW ).

Question
Pourquoi l’algorithme n’est il pas polynomial ?

A. Parmentier, ENPC 12 décembre 2018 7 / 43

Programmation dynamique

x(j, W 0 ) = valeur maximale d’un sac de capacité W 0 , en se limitant aux

j premiers objets.
Equation (programmation dynamique)

x(j, W 0 ) = max(x(j − 1, W 0 ), x(j − 1, W 0 − wj ) + cj ).

Complexité : O(nW ).

Question
Pourquoi l’algorithme n’est il pas polynomial ?

Ce n’est pas polynomial car W nécessite log2 (W ) bits pour être codés.
C’est un algorithme pseudo-polynomial.

A. Parmentier, ENPC 12 décembre 2018 7 / 43

Formulation sous forme de programme linéaire en nombres entiers

Donner un programme linéaire en nombres entiers pour ce problème.

A. Parmentier, ENPC 12 décembre 2018 8 / 43

Formulation sous forme de programme linéaire en nombres entiers

Donner un programme linéaire en nombres entiers pour ce problème.

n
X
max cj xj
j=1
n
X
s.c. wj xj ≤ W
j=1
xj ∈ {0, 1} pour tout j ∈ {1, . . . , n}

A. Parmentier, ENPC 12 décembre 2018 8 / 43

Calcul de la relaxation linéaire

La borne supérieure
n
X
max cj xj
j=1
n
X
s.c. wj xj ≤ W
j=1
0 ≤ xj ≤ 1 pour tout j ∈ {1, . . . , n}

peut facilement se calculer avec un solver.

Exercice
Donner un algorithme très simple qui calcule la solution du relâché
continu.

A. Parmentier, ENPC 12 décembre 2018 9 / 43

 Solution du relâché continu
Pn
On suppose que j=1 wj > W et que pour tout j, wj ≤ W , sinon trivial !

I Classer les objets de façon à ce que

c1 c2 cn
≥ ≥ ... ≥ .
w1 w2 wn

I Poser x1 = x2 = · · · = xj̄ := 1 avec j̄ le plus grand entier tel que

Pj̄
j=1 wj ≤ W .
Pj̄
W − j=1 wj
I Poser xj̄+1 := wj̄+1
.
I Poser xj̄+2 = . . . = xn := 0.

Lemme
Un tel x est solution optimale de la relaxation.
A. Parmentier, ENPC 12 décembre 2018 10 / 43
Heuristique avec garantie

Algorithme fournissant une solution valant toujours au moins la moitié

de la valeur optimale :

On suppose qu wj ≤ W pour tout j.

cj
On reprend l’indexation par wj
et le j du relâché linéaire.

Pj̄+1
I j=1 cj est une borne supérieure de la valeur optimale OPT .
I {1, . . . , j̄} et {j̄ + 1} sont deux solutions réalisables, l’une des deux
Pj̄+1
étant par conséquent au moins de valeur ≥ 12 j=1 cj , i.e. de valeur
≥ 21 OPT .

A. Parmentier, ENPC 12 décembre 2018 11 / 43

Sommaire de la partie

1. Sac à dos

2. Bin Packing

3. Positionnement d’entrepôts

4. Exercices

A. Parmentier, ENPC 12 décembre 2018 12 / 43

 Formalisation du bin-packing

BIN-PACKING
Données. Entiers positifs ou nuls a1 , . . . , an et W .
Tâche.
P Trouver un entier naturel k et une fonction f : [n] → [k ] avec
i: f (i)=j ai ≤ W pour tout j ∈ [k ] tels que k soit minimum.

Interprétation : conteneurs de taille W , objets de tailles ai . Mettre tous

les objets dans un nombre minimum de conteneurs (f indique
l’affectation des objets aux conteneurs).

A. Parmentier, ENPC 12 décembre 2018 13 / 43

Applications (et généralisation en plusieurs dimensions)

Application 1. Stockage optimal (entrepôts), transport optimal

(camions) ; souvent, il y a des contraintes de forme ou de volume en
plus (bin-packing 2D ou 3D)

Application 2. Découpe : on a des poutres de longueur fixée, on a une

commande pour des longueurs a1 , . . . , an ; minimiser le nombre de
poutres utilisées.

Application 3. Copier un disque dur avec le moins de clés USB possible.

A. Parmentier, ENPC 12 décembre 2018 14 / 43

Complexité

Théorème
BIN-PACKING est NP-difficile.

A. Parmentier, ENPC 12 décembre 2018 15 / 43

Un cas particulier facile

Exercice
Supposons qu’un instance a1 , . . . , an du bin-packing soit telle que
ai 1
> pour tout i = 1, . . . , n.
W 3
Donner un algorithme polynomial pour résoudre ce cas particulier.

A. Parmentier, ENPC 12 décembre 2018 16 / 43

Un cas particulier facile

Exercice
Supposons qu’un instance a1 , . . . , an du bin-packing soit telle que
ai 1
> pour tout i = 1, . . . , n.
W 3
Donner un algorithme polynomial pour résoudre ce cas particulier.

Couplage biparti

A. Parmentier, ENPC 12 décembre 2018 16 / 43

 Borne inférieure

BIN-PACKING
Données. Entiers positifs ou nuls a1 , . . . , an et W .
Tâche.
P Trouver un entier naturel k et une fonction f : [n] → [k ] avec
i: f (i)=j ai ≤ W pour tout j ∈ [k ] tels que k soit minimum.

Donner une borne inférieure simple à la valeur de BIN-PACKING

A. Parmentier, ENPC 12 décembre 2018 17 / 43

 Borne inférieure

BIN-PACKING
Données. Entiers positifs ou nuls a1 , . . . , an et W .
Tâche.
P Trouver un entier naturel k et une fonction f : [n] → [k ] avec
i: f (i)=j ai ≤ W pour tout j ∈ [k ] tels que k soit minimum.

Donner une borne inférieure simple à la valeur de BIN-PACKING

& '
X ai
≤ OPT
i=1n
W

A. Parmentier, ENPC 12 décembre 2018 17 / 43

Formulation programme linéaire

Donner un PLNE modélisant le problème

A. Parmentier, ENPC 12 décembre 2018 18 / 43

 Formulation programme linéaire

Donner un PLNE modélisant le problème

On suppose que l’on a k conteneurs disponibles.

k
X
min zj
j=1
Xk
s.c. yji = 1 i = 1, . . . , n
j=1
n
X
ai yji ≤ Wzj j = 1, . . . , k
i=1
yji , zj ∈ {0, 1} i = 1, . . . , n; j = 1, . . . , k

où zj = 1 si le conteneur j est utilisé et yji = 1 si l’objet i est mis dans

le conteneur j.
A. Parmentier, ENPC 12 décembre 2018 18 / 43
Heuristiques

1. NEXT-FIT : 2-approximation.
17
2. FIRST-FIT : 10
-approximation.
3. FIRST-FIT DECREASING : 32 -approximation.

Peut-on faire mieux ?

A. Parmentier, ENPC 12 décembre 2018 19 / 43

Heuristiques

1. NEXT-FIT : 2-approximation.
17
2. FIRST-FIT : 10
-approximation.
3. FIRST-FIT DECREASING : 32 -approximation.

Théorème
A moins que P = NP il n’existe pas d’algorithme polynomial garan-
tissant une approximation ρ < 23

Exercice
1. Prouver que l’existence d’une solution à 2 bin est NP-complet en
le réduisant depuis le problème partition.
2. En déduire le théorème.

A. Parmentier, ENPC 12 décembre 2018 19 / 43

NEXT-FIT

Je prends les objets les uns après les autres. Dès que l’objet i ne peut
pas entrer dans le conteneur courante, je passe à un nouveau
conteneur.

Théorème
NEXT-FIT fournit une solution SOL telle que

SOL ≤ 2OPT − 1.

Sur quoi repose la preuve ?

A. Parmentier, ENPC 12 décembre 2018 20 / 43

NEXT-FIT

Je prends les objets les uns après les autres. Dès que l’objet i ne peut
pas entrer dans le conteneur courante, je passe à un nouveau
conteneur.

Théorème
NEXT-FIT fournit une solution SOL telle que

SOL ≤ 2OPT − 1.

Proof.
SOL
X X  
ai > W donne ai > W
i
2
i : f (i)∈{2j−1,2j}
& '
X ai
et la borne inférieure ≤ OPT donne le résultat.
i=1n
W
A. Parmentier, ENPC 12 décembre 2018 20 / 43
NEXT-FIT

Je prends les objets les uns après les autres. Dès que l’objet i ne peut
pas entrer dans le conteneur courante, je passe à un nouveau
conteneur.

Théorème
NEXT-FIT fournit une solution SOL telle que

SOL ≤ 2OPT − 1.

Exercice : petits objets

ai
Montrer que si l’instance I satisfait W ≤ γ pour tout i, alors
 P
i ai OPT (I)
  
NF (I) ≤ ≤
W (1 − γ) 1−γ

A. Parmentier, ENPC 12 décembre 2018 20 / 43

FIRST-FIT

Je prends les objets les uns après les autres. Je mets l’objet i dans le
conteneur de plus petit rang où il peut entrer.

Théorème
FIRST-FIT fournit une solution SOL telle que

17
 
SOL ≤ OPT .
10

A. Parmentier, ENPC 12 décembre 2018 21 / 43

FIRST-FIT DECREASING

Je trie d’abord les objets par ai décroissant. Puis j’applique FIRST-FIT.

Théorème
FIRST-FIT DECREASING fournit une solution SOL telle que

3
SOL ≤ OPT .
2

A. Parmentier, ENPC 12 décembre 2018 22 / 43

Quel avantage pratique ont NEXT-FIT et FIRST-FIT sur FIRST-FIT
DECREASING ?

A. Parmentier, ENPC 12 décembre 2018 23 / 43

 Quel avantage pratique ont NEXT-FIT et FIRST-FIT sur FIRST-FIT
DECREASING ?
L’avantage de NEXT-FIT et de FIRST-FIT sur FIRST-FIT DECREASING
est qu’ils peuvent fonctionner on-line.

A. Parmentier, ENPC 12 décembre 2018 23 / 43

Exemple de Recherche locale

On résout le problème de manière indirecte : on cherche à savoir s’il

existe une solution en k conteneurs.
I Choisir W 0 ≥ W , une capacité commune, pour laquelle il existe une
solution réalisable.
I Appliquer une recherche locale pour minimiser W 0 : passage d’une
solution à une solution voisine en changeant l’affectation d’un objet.
I Si à la fin W 0 ≤ W : solution réalisable au problème de départ en k
conteneurs.

On répète l’algorithme en faisant varier le nombre k .

A. Parmentier, ENPC 12 décembre 2018 24 / 43

Problème ouvert

Il existe encore de nombreuses instances non résolues : par exemple :

W = 150
n = 120
ai = 100 22 25 51 95 58 97 30 79 23 53 80 20 65 64 21 26 100 81 98
70 85 92 97 86 71 91 29 63 34 67 23 33 89 94 47 100 37 40 58 73 39
49 79 54 57 98 69 67 49 38 34 96 27 92 82 69 45 69 20 75 97 51 70 29
91 98 77 48 45 43 61 36 82 89 94 26 35 58 58 57 46 44 91 49 52 65 42
33 60 37 57 91 52 95 84 72 75 89 81 67 74 87 60 32 76 85 59 62 39 64
52 88 45 29 88 85 54 40 57

Meilleure solution connue : k = 51

A. Parmentier, ENPC 12 décembre 2018 25 / 43

Sommaire de la partie

1. Sac à dos

2. Bin Packing

3. Positionnement d’entrepôts

4. Exercices

A. Parmentier, ENPC 12 décembre 2018 26 / 43

Présentation du problème

De nombreuses décisions économiques mettent en jeu la sélection ou

le positionnement de dépôts, d’usines, de relais, d’hôpitaux, etc. afin de
répondre de manière optimale à la demande.

A. Parmentier, ENPC 12 décembre 2018 27 / 43

Illustration

Emplacement potentiel d’un entrepôt

Client

A. Parmentier, ENPC 12 décembre 2018 28 / 43

Illustration

A. Parmentier, ENPC 12 décembre 2018 29 / 43

Formalisation du problème

Problème du positionnement d’entrepôts.

Données. Clients D, entrepôts potentiels F , coût fixe fi ∈ R+
d’ouverture pour entrepôt i ∈ F , coût de service cij ∈ R+ pour
i ∈ F et j ∈ D.
Demande. Trouver X ⊆ F et affectation σ : D → X tels que
X X
fi + cσ(j)j
i∈X j∈D

soit minimale.

A. Parmentier, ENPC 12 décembre 2018 30 / 43

Complexité

Proposition
Le problème du positionnement d’entrepôts est NP-difficile.

A. Parmentier, ENPC 12 décembre 2018 31 / 43

Formulation sous forme PLNE

Donner un PLNE qui modélise le problème de positionnement d’en-

trepôts.

A. Parmentier, ENPC 12 décembre 2018 32 / 43

Formulation sous forme PLNE

Donner un PLNE qui modélise le problème de positionnement d’en-

trepôts.

X XX
Min fi yi + cij xij
i∈F i∈F j∈D
ij ≤ yi
s.c. xX i ∈ F, j ∈ D
xij = 1 j ∈D
i∈F
xij ∈ {0, 1} i ∈ F, j ∈ D
yi ∈ {0, 1} i ∈ F.

A. Parmentier, ENPC 12 décembre 2018 32 / 43

Recherche locale

1. Comment encoder une solution ?

2. Quel voisinage proposez vous ?

A. Parmentier, ENPC 12 décembre 2018 33 / 43

Recherche locale

1. Comment encoder une solution ?

2. Quel voisinage proposez vous ?

1. Le voisinage naturel est basé sur la remarque suivante : L’espace

des solutions peut être identifié à l’ensemble des parties X de F .

A. Parmentier, ENPC 12 décembre 2018 33 / 43

Recherche locale

1. Comment encoder une solution ?

2. Quel voisinage proposez vous ?

1. Le voisinage naturel est basé sur la remarque suivante : L’espace

des solutions peut être identifié à l’ensemble des parties X de F .

2. Modifications locales efficaces : passer de X à X 0 avec
2.1 X 0 := X \ {x} pour un x ∈ X , (drop)
2.2 X 0 := X ∪ {x 0 } pour un x 0 ∈ F \ X (add) ou
2.3 X 0 := X \ {x} ∪ {x 0 } (swap).

A. Parmentier, ENPC 12 décembre 2018 33 / 43

Exercice

On reprend le problème de positionnement d’entrepôts vu en cours,

mais avec cette fois une contrainte supplémentaire : chaque entrepôt
ne peut desservir qu’un nombre limité de clients. Modéliser le problème
suivant comme un problème linéaire en nombres entiers.
Données : Un ensemble fini de clients D, un ensemble fini d’entrepôts
potentiels F , un coût fixe fi ∈ R+ d’ouverture et une capacité Ki pour
chaque entrepôt i ∈ F , et un coût de service cij ∈ R+ pour chaque
i ∈ F et j ∈ D.
Demande : Trouver un sous-ensemble X ⊆ F (dits entrepôts ouverts)
et une affectation σ : D → X des clients aux entrepôts ouverts, tel que
pour tout i, l’entrepôt i ne desserve pas plus de Ki clients, de façon à
ce que la quantité X X
fi + cσ(j)j
i∈X j∈D

soit minimale.
A. Parmentier, ENPC 12 décembre 2018 34 / 43
Correction

X XX
Min fi yi + cij xij
i∈F
X i∈F j∈D
s.c. xij ≤ Ki yi i ∈F
j∈D
X
xij = 1 j ∈D
i∈F
xij ∈ {0, 1} i ∈ F, j ∈ D
yi ∈ {0, 1} i ∈ F.

A. Parmentier, ENPC 12 décembre 2018 35 / 43

Sommaire de la partie

1. Sac à dos

2. Bin Packing

3. Positionnement d’entrepôts

4. Exercices
4.1 Inégalités valides
4.2 Relaxation Lagrangienne

A. Parmentier, ENPC 12 décembre 2018 36 / 43

Inégalité valide : rappel

Une inégalité valide n’a d’intérêt que si elle réduit la taille du polytope !

A. Parmentier, ENPC 12 décembre 2018 37 / 43

Inégalité valide pour le sac à dos

On considère un problème de sac-à-dos avec a1 , . . . , an , b des réels

positifs. On note S l’ensemble des solutions réalisables
n
( )
X
n
S := x ∈ {0, 1} : ai xi ≤ b .
i=1
On appelle
P ensemble dépendant tout ensemble C ⊆ {1, . . . , n} tel
que i∈C ai > b.
1. Montrer que tout x ∈ S satisfait l’inégalité
X
xi ≤ |C| − 1,
i∈E(C)

où E(C) = C ∪ {j : aj ≥ maxi∈C ai }.
2. Est-ce le cas pour des solutions du relâché continu.
3. Supposons que le résolve le relâché continu : comment identifier
l’ensemble C pour lequel la contrainte est la plus violée ? A quoi cela
sert-il ?
A. Parmentier, ENPC 12 décembre 2018 38 / 43
Correction

1. C n’est pas faisable, donc au plus |C − 1| éléments sont

sélectionnés à l’intérieur.
2. Par exemple, si l’on deux items de poids ai = 2, une capacité
W = 3, et C = {1, 2}, alors la solution du relâché linéaire x1 = 1 et
x2 = 1/2 viole l’inégalité valide.
De manière générale, il suffit par exemple de prendre la solution
optimale du relâché continu pour avoir un contre exemple. (presque
sûrement par rapport à la mesure uniforme sur les instances).

3. Par exemple par programmation dynamique (ou par un problème de

plus court chemin sous-contrainte.)

A. Parmentier, ENPC 12 décembre 2018 39 / 43

 Inégalité valide pour le bin-packing

On rappelle la modélisation PLNE du problème du bin-packing. On

suppose que l’on dispose d’un stock de K boîtes de taille 1.
PK
min zj
Pj=1K
s.c. yji = 1 pour i = 1, . . . , n
Pj=1n
i=1 ai yji ≤ zj pour j = 1, . . . , K
yji , zi ∈ {0, 1} pour i = 1, . . . , n;
j = 1, . . . , K
où zj = 1 si la boîte j est utilisée et yji = 1 si l’objet i est mis dans la
boîte j.
1. Montrer qu’en ajoutant les contraintes zj ≥ zj+1 , pour
j = 1, . . . , K − 1, on continue à modéliser le problème du
bin-packing.
2. Même question avec la contrainte K
P Pn 
j=1 zj ≥ i=1 ai .
3. Expliquer l’intérêt de ce type d’inégalité dans une résolution d’un
problème de bin-packing dans une approche branch-and-bound.
A. Parmentier, ENPC 12 décembre 2018 40 / 43
Correction

1. Cela oblige juste à utiliser les premiers conteneurs, mais n’impacte

pas la valeur de la solution optimale.
2. Borne inférieure que l’on a donné.
K

3. Briser la symétrie pour la première (très important) : divise par OPT
la taille de l’ensemble des solutions optimales. Restreindre la taille
du polytope pour la seconde.

A. Parmentier, ENPC 12 décembre 2018 41 / 43

Relaxation Lagrangienne pour le bin packing

On rappelle le PLNE pour le bin-packing

k
X
min zj
j=1
Xk
s.c. yji = 1 i = 1, . . . , n
j=1
n
X
ai yji ≤ Wzj j = 1, . . . , k
i=1
yji , zj ∈ {0, 1} i = 1, . . . , n; j = 1, . . . , k

1. Procéder à la relaxation Lagrangienne de kj=1 yji = 1

P

2. Montrer que la borne zRL (λ) se calcule facilement (quel problème

doit on résoudre à chaque fois)
3. Montrer que la borne donnée par la relaxation lagrangienne est
meilleure que la borne donnée par la relaxation linéaire
A. Parmentier, ENPC 12 décembre 2018 42 / 43
Relaxation Lagrangienne pour le bin packing

La correction est dans le nouveau poly, Section 11.3.1

A. Parmentier, ENPC 12 décembre 2018 43 / 43