Problème du sac à dos¶
Ce TD accompagne le chapitre Algorithmes d'approximation, algorithmes probabilistes.
On considère le problème suivant :
Problème : Knapsack
- Entrée :
- \(n\) objets numérotés de \(1\) à \(n\) ;
- à chaque objet on associe deux entiers : \(w_i > 0\) son poids et \(v_i > 0\) sa valeur ;
- un poids maximal \(W \in \N\).
-
Sortie : pour \(S \subset \range{1}{n}\), on note \(w(S) = \sum_{x \in S} w_x\) et \(v(S) = \sum_{x \in S} v_x\). On cherche
\[ \max \enscomp{v(S)}{S \subset \range{1}{n}, w(S) \le W} \]
On cherche ainsi la valeur maximale d'un ensemble d'objets dont le poids est sous la limite.
Cas fractionnaire et algorithme glouton¶
On considère ici une variante où on peut prendre partiellement les objets.
Problème : FractionalKnapsack
- Entrée : les mêmes données que pour
Knapsack. -
Sortie : pour \(\sigma : \range{1}{n} \rightarrow \Q_+ \cap [0;1]\), on note \(w(\sigma) = \sum_{x = 1}^{n} w_x \sigma(x)\) et \(v(\sigma) = \sum_{x = 1}^{n} v_x \sigma(x)\). On cherche
\[ \max \enscomp{v(\sigma)}{\sigma : \range{1}{n} \rightarrow \Q_+ \cap [0;1], w(\sigma) \le W} \]
Pour chaque objet, on calcule son efficacité \(e_i = v_i / w_i\). On trie alors les objets par efficacité décroissante et on sélectionne tous les objets tant qu'on reste sous le poids, le premier objet qui force un dépassement est placé de manière fractionnelle.
C'est un algorithme glouton. On va montrer qu'il renvoie une solution optimale.
On va se placer dans le cas où \(\sum_{i=1}^n w_i > W\) (sinon, prendre tous les objets en entier est optimal).
Question 1. En déduire que si \(\tau\) est une solution optimale, alors \(w(\tau) = W\).
Corrigé
Si \(w(\tau) < W\), comme \(\sum w_i > W\), il existe un objet \(i\) avec \(\tau(i) < 1\). On peut alors augmenter \(\tau(i)\) de \(\min\left(1 - \tau(i), \frac{W - w(\tau)}{w_i}\right) > 0\) sans dépasser \(W\), ce qui augmente strictement la valeur car \(v_i > 0\) : contradiction.
On suppose qu'on a obtenu une solution gloutonne donnée par \(\sigma\) et qu'on dispose également d'une solution optimale \(\tau\). Pour simplifier, on peut supposer les objets rangés par efficacité décroissante, ainsi \(1\) est l'objet d'efficacité maximale, et \(\sigma(1) = \min\left(1, \frac{W}{w_1}\right)\).
Question 2. Montrer que si \(\sigma(1) > \tau(1)\), alors on peut en déduire une solution optimale \(\tau'\) telle que \(\tau'(1) = \sigma(1)\).
Corrigé
On pose \(\delta W = (\sigma(1) - \tau(1)) w_1 > 0\). Comme \(w(\tau) = W\), on a \(\sum_{i=2}^n \tau(i) w_i = W - \tau(1) w_1\), et \(W - \tau(1) w_1 = (W - \sigma(1) w_1) + \delta W > 0\) car \(\sigma(1) w_1 \le W\). On pose alors \(\chi = \frac{\delta W}{W - \tau(1) w_1}\), on a
or, \(\sigma(1) w_1 \le W\) donc \(\delta W \le W - \tau(1) w_1\), c'est-à-dire \(\chi \le 1\).
On définit ainsi \(\tau'\) par
qui est bien à valeurs dans \([0;1]\). On a
Et
car \(\frac{v_1}{w_1} \ge \frac{v_i}{w_i}\).
Ainsi, on a \(\tau'\) solution admissible et par maximalité, \(v(\tau') = v(\tau)\) et \(\tau'\) est optimale. Or \(\tau'(1) = \sigma(1)\).
Question 3. Justifier que si \(\tau\) est optimale pour les objets de \(1\) à \(n\), alors \(\tau^*\) la restriction de \(\tau\) à \(\range{2}{n}\) est également optimale pour cette instance avec \(W - \tau(1) w_1\) comme poids limite.
Corrigé
\(\tau^*\) est admissible : \(w(\tau^*) = w(\tau) - \tau(1) w_1 \le W - \tau(1) w_1\). Si une solution \(\rho\) des objets \(2\) à \(n\) avec ce poids limite vérifiait \(v(\rho) > v(\tau^*)\), en la complétant par \(\tau(1)\) pour l'objet \(1\), on obtiendrait une solution admissible de l'instance initiale de valeur \(\tau(1) v_1 + v(\rho) > v(\tau)\) : contradiction.
Question 4. Justifier que \(\sigma^*\), la restriction de \(\sigma\) à \(\range{2}{n}\), est également donnée par l'algorithme glouton pour les objets de \(2\) à \(n\) et le poids limite \(W-\sigma(1) w_1\).
Question 5. En déduire, par récurrence sur le nombre d'objets, que le
glouton renvoie une solution optimale et ainsi que FractionalKnapsack est
dans P.
Corrigé
Par récurrence sur \(n\), le cas \(n = 0\) étant trivial. Si \(\sum w_i \le W\), le glouton prend tout, ce qui est optimal. Sinon, soit \(\tau\) optimale ; on a \(\tau(1) \le \sigma(1)\) car \(\sigma(1)\) est la plus grande valeur admissible, et par la question 2 on peut supposer \(\tau(1) = \sigma(1)\). Par la question 3, \(\tau^*\) est optimale pour les objets \(2\) à \(n\) et le poids \(W - \sigma(1) w_1\) ; par la question 4 et l'hypothèse de récurrence, \(\sigma^*\) aussi, donc \(v(\sigma^*) = v(\tau^*)\) et \(v(\sigma) = \sigma(1) v_1 + v(\sigma^*) = v(\tau)\).
Le glouton se résume à un tri et un parcours : il est en \(O(n \log n)\),
donc FractionalKnapsack est dans P.
Pseudo-polynomialité¶
On fixe ici une instance de Knapsack.
On considère \(V = \max_{i=1}^n v_i\) la valeur maximale d'un objet. On sait que \(nV\) est un majorant direct de la solution optimale.
On va alors poser pour \(i \in \range{0}{n}\) et \(p \in \range{0}{nV}\), \(A(i,p)\) le plus petit poids d'un sous-ensemble des objets \(\le i\) dont la valeur est exactement \(p\). Quand un tel sous-ensemble n'existe pas, on pose \(A(i,p) = \infty\).
Question 6. Déterminer les valeurs pour lesquelles on peut directement calculer \(A(i,p)\).
Corrigé
On a \(A(i,0) = 0\) pour tout \(i\) et \(A(0,p) = \infty\) pour \(p > 0\).
Question 7. Déterminer une équation de Bellman pour \(A\).
Corrigé
Soit \(i \ge 1\) et \(p \in \range{1}{nV}\), si \(v_i > p\), alors on ne peut pas utiliser l'objet \(i\), donc \(A(i, p) = A(i-1, p)\). Sinon, utiliser l'objet \(i\) va permettre au mieux un poids de \(w_i + A(i-1,p-v_i)\), qui n'a pas de raison d'être a priori meilleur que \(A(i-1,p)\), on prend donc le minimum :
Question 8. En déduire un algorithme calculant la solution de Knapsack
en \(O(n^2 V)\).
Corrigé
On remplit le tableau \(A\) de taille \((n+1) \times (nV + 1)\) ligne par ligne avec l'équation précédente, chaque case en \(O(1)\), soit \(O(n^2 V)\). La valeur optimale est \(\max \enscomp{p \in \range{0}{nV}}{A(n,p) \le W}\). Pour obtenir les objets, on remonte depuis la case \((n, p)\) optimale : si \(A(i,p) = A(i-1,p)\), on passe à \((i-1,p)\), sinon on prend l'objet \(i\) et on passe à \((i-1, p - v_i)\). Une implémentation en C est donnée dans le TP.
Question 9. On a Knapsack dans P si l'instance est donnée sous quelle
représentation ?
Corrigé
Si les valeurs sont données en unaire, alors \(V\) est de l'ordre de la taille des données, donc la solution en programmation dynamique est polynomiale. En binaire, la taille de l'entrée est de l'ordre de \(n \log V\) et \(n^2 V\) est exponentiel en cette taille : on dit que l'algorithme est pseudo-polynomial.
Schéma d'approximation polynomial complet¶
Soit \(0 < \epsilon < 1\). On va montrer qu'il est possible d'obtenir en temps polynomial en \(n\) et \(\frac{1}{\epsilon}\) une solution de valeur au moins \((1-\epsilon) OPT\), c'est-à-dire une \(\frac{1}{1-\epsilon}\)-approximation au sens du chapitre, où \(\frac{1}{1-\epsilon} = 1 + \epsilon + o(\epsilon)\). Quitte à les éliminer, on suppose que chaque objet rentre seul dans le sac : \(w_i \le W\) pour tout \(i\).
On pose \(K = \frac{\epsilon V}{n}\) et pour chaque objet \(i\), on définit une nouvelle valeur \(v'_i = \left\lfloor \frac{v_i}{K} \right\rfloor\). On calcule alors une solution optimale \(S'\) avec ces nouvelles valeurs par l'algorithme de programmation dynamique de la partie précédente et on renvoie \(S'\).
Question 10. Calculer la complexité de cette résolution.
Corrigé
On a \(V' = \max v'_i \le \max \frac{v_i}{K} = \frac{V}{K} = \frac{n}{\epsilon}\), donc la complexité est en \(O(n^2 V') = O(n^3 \frac{1}{\epsilon})\).
Question 11. Montrer que \(v(S') \ge (1-\epsilon) OPT\) où \(OPT\) est la valeur optimale.
Corrigé
Soit \(S^*\) une solution optimale pour les valeurs \(v_i\) : c'est aussi une solution admissible pour les valeurs \(v'_i\) (les poids n'ont pas changé). Comme \(S'\) est optimale pour les \(v'_i\) et que \(K v'_x \le v_x\) et \(K v'_x > v_x - K\) :
Or chaque objet rentre seul dans le sac, donc \(OPT \ge V\), et ainsi \(v(S') \ge (1-\epsilon) OPT\).
Les schémas d'approximation polynomiaux complets sont très fortement liés à la pseudo-polynomialité.
NP-complétude¶
On s'intéresse ici au problème de décision associé à Knapsack : étant donné
de plus un seuil \(k\), existe-t-il un sous-ensemble \(S\) tel que \(w(S) \le W\) et
\(v(S) \ge k\) ?
Question 12. Montrer que Knapsack est dans NP.
Pour montrer que Knapsack est NP-complet, on va utiliser un problème
intermédiaire ExactCover et effectuer la chaîne de réduction :
On rappelle Coloration dont on a montré qu'il était NP-complet par réduction
de 3-Coloriable lui-même par réduction de 3-SAT.
Problème : Coloration
- Entrée : un graphe non orienté \(G = (S,A)\) et un entier \(k\).
- Sortie : existe-t-il une application \(\gamma : S \rightarrow \range{1}{k}\) telle que \(\forall \{x,y\} \in A, \gamma(x) \neq \gamma(y)\) ?
Le problème ExactCover est une variante des problèmes déjà rencontrés de
couverture :
Problème : ExactCover
- Entrée : un ensemble fini \(\Sigma\) et une suite de sous-ensembles \(S_1, \dots, S_n \subset \Sigma\).
- Sortie : existe-t-il une sous-famille \(1 \le i_1 < \dots < i_k \le n\) telle que les \(S_{i_j}\) soient deux à deux disjoints et que \(\bigcup_{j=1}^k S_{i_j} = \bigcup_{j=1}^n S_j\) ? (Autrement dit, peut-on extraire une partition de \(\bigcup_j S_j\) parmi les \(S_i\) ?)
Question 13. Montrer que ExactCover est dans NP.
Question 14. On considère une instance de Coloration donnée par un
graphe \(G = (V,A)\) et un entier \(k\). On fixe un ordre total sur \(V\) et on note
chaque arête \(a = \{x_a, y_a\}\) avec \(x_a < y_a\). On pose
et on considère les sous-ensembles suivants :
Montrer qu'on a défini ainsi une réduction polynomiale de Coloration vers
ExactCover.
Question 15. On considère une instance de ExactCover donnée par
\(\Sigma\) et \(S_1, \dots, S_n \subset \Sigma\). Sans perte de généralité, on peut
supposer que \(\Sigma = \bigcup_{j=1}^n S_j = \range{1}{p}\).
Pour \(i \in \range{1}{p}, j \in \range{1}{n}\), on pose \(\epsilon_{i,j} = \begin{cases} 0 & \text{si } i \not \in S_j \\ 1 & \text{sinon.} \end{cases}\)
On pose également \(d = n+1\) et à chaque sous-ensemble \(S_j\), on associe l'entier \(a_j = \sum_{i=1}^p \epsilon_{i,j} d^{i-1}\).
On pose également \(W = d^0 + \dots + d^{p-1}\).
On va considérer l'instance du sac à dos avec \(W\) comme poids maximal et pour chaque objet \(j \in \range{1}{n}\), \(w_j = v_j = a_j\). On considère alors \(W\) comme seuil.
- Détailler la construction pour \(S_1 = \{ 1\}, S_2 = \{ 3, 4 \}, S_3 = \{ 1, 2, 4 \}, S_4 = \{ 1, 2 \}\) et \(S_5 = \{2, 3, 4\}\).
- Montrer qu'on a ainsi défini une réduction polynomiale de
ExactCoveràKnapsacket en déduire queKnapsackest NP-complet.
Corrigé (1.)
Ici \(n = 5\), \(d = 6\) et \(\Sigma = \range{1}{4}\) (la source prenait \(\Sigma = \range{1}{5}\), mais \(5\) n'appartient à aucun \(S_j\)). On écrit les \(a_j\) en base \(6\), le chiffre de rang \(i - 1\) indiquant si \(i \in S_j\) :
| \(j\) | \(S_j\) | base 6 | \(a_j\) |
|---|---|---|---|
| 1 | \(\{1\}\) | \(0001\) | \(1\) |
| 2 | \(\{3,4\}\) | \(1100\) | \(252\) |
| 3 | \(\{1,2,4\}\) | \(1011\) | \(223\) |
| 4 | \(\{1,2\}\) | \(0011\) | \(7\) |
| 5 | \(\{2,3,4\}\) | \(1110\) | \(258\) |
et \(W = 1111_6 = 259\). Les sous-ensembles d'objets de poids total exactement \(259\) sont \(\{1, 5\}\) (\(1 + 258\)) et \(\{2, 4\}\) (\(252 + 7\)), qui correspondent aux deux partitions \(S_1 \cup S_5\) et \(S_2 \cup S_4\). Comme on additionne au plus \(n < d\) chiffres égaux à \(1\), il n'y a jamais de retenue : c'est le rôle du choix \(d = n + 1\).