Les énoncés des TPs 1, 2 et 3 sont disponibles dans le dossier TP1/Sujets.
Membres du groupe :
- Maximilien Goujon
- Kilian Giraud
- Théo Berr
Ces TPs portent sur l'implémentation et l'analyse d'algorithmes d'optimisation appliqués au problème du sac à dos unidimensionnel (0/1 Knapsack). L'objectif est d'implémenter plusieurs approches : relaxation linéaire, heuristique gloutonne, programmation dynamique, prétraitement de variables et de comparer leurs performances en termes de temps d'exécution et de qualité des solutions obtenues.
On dispose de
Les objets sont générés aléatoirement, chacun représenté par un couple (poids, profit). Sur l'instance instance3.csv, les 20 objets générés sont :
| Objet | Poids | Profit |
|---|---|---|
| 1 | 24 | 614 |
| 2 | 61 | 682 |
| 3 | 43 | 137 |
| 4 | 37 | 544 |
| 5 | 66 | 326 |
| 6 | 20 | 598 |
| 7 | 65 | 699 |
| 8 | 31 | 709 |
| 9 | 62 | 742 |
| 10 | 93 | 330 |
| 11 | 50 | 785 |
| 12 | 91 | 985 |
| 13 | 79 | 168 |
| 14 | 94 | 938 |
| 15 | 69 | 334 |
| 16 | 51 | 898 |
| 17 | 74 | 689 |
| 18 | 90 | 372 |
| 19 | 89 | 879 |
| 20 | 56 | 16 |
La relaxation linéaire remplace la contrainte d'intégrité
Résultats sur instance3.csv (capacité = 53, n = 12) :
- Valeur optimale LP : 80
La relaxation linéaire fournit une borne supérieure de l'optimum entier. La solution peut inclure un objet fractionné et n'est pas nécessairement réalisable pour le problème 0/1.
Complexité :
L'heuristique gloutonne applique le même tri par ratio décroissant, mais ne prend un objet que s'il tient entièrement dans le sac. La solution produite est toujours réalisable.
Résultats sur instance3.csv :
- Solution :
x = [ 1 1 1 1 1 1 0 0 1 0 0 0 ] - Poids total : 52 / 53
- Valeur totale : 78
La valeur obtenue (78) est légèrement inférieure à la borne LP (80), ce qui est attendu : le glouton perd la fraction d'objet que la LP autorisait. L'écart relatif ici est d'environ 2,5 %, ce qui montre que l'heuristique est très proche de l'optimum sur cette instance.
Complexité :
On fixe le nombre d'objets et on fait varier la capacité
| b | Temps LP (s) | Temps Greedy (s) |
|---|---|---|
| 100 | 0.001 | 0.001 |
| 200 | 0.003 | 0.002 |
| 800 | 0.002 | 0.001 |
| 1600 | 0.001 | 0.001 |
| 2000 | 0.002 | 0.001 |
| 2500 | 0.001 | 0.002 |
| 3000 | 0.001 | 0.002 |
Les deux algorithmes ont une complexité en
On fixe la capacité et on fait varier le nombre d'objets
| n | Temps LP (s) | Temps Greedy (s) |
|---|---|---|
| 5 | 0.000 | 0.000 |
| 20 | 0.001 | 0.000 |
| 25 | 0.001 | 0.001 |
| 50 | 0.002 | 0.001 |
| 70 | 0.003 | 0.002 |
| 90 | 0.003 | 0.002 |
| 100 | 0.002 | 0.001 |
Les temps croissent avec
La programmation dynamique résout le problème de manière exacte en construisant un tableau
Résultats sur instance3.csv :
Z = (0, 0, 0, 0, 0, 5, 8, 14, 14, 14, 15, 15, 19, 22, 27, 27, 27, 29, 29, 32,
35, 37, 37, 37, 42, 42, 42, 45, 45, 47, 50, 52, 52, 52, 55, 55, 57, 60,
60, 62, 63, 65, 65, 65, 67, 70, 70, 73, 73, 75, 75, 75, 78, 78)
D = (0, 0, 0, 0, 0, 9, 5, 1, 1, 1, 3, 3, 9, 5, 2, 2, 2, 3, 3, 9, 5, 4, 4, 4,
3, 3, 3, 5, 5, 7, 5, 4, 4, 4, 6, 6, 9, 5, 5, 7, 6, 6, 6, 6, 9, 7, 7, 6,
6, 7, 7, 7, 9, 9)
x* = (1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0)
La solution optimale entière vaut 78, identique à la solution gloutonne sur cette instance. La programmation dynamique garantit l'optimalité, contrairement au glouton qui peut rater l'optimum.
Complexité :
On fixe le nombre d'objets et on fait varier la capacité
| b | Temps KP Dynamic (s) |
|---|---|
| 100 | 0.016 |
| 200 | 0.017 |
| 800 | 0.056 |
| 1600 | 0.105 |
| 2000 | 0.141 |
| 2500 | 0.158 |
| 3000 | 0.199 |
L'algorithme a une compléxité de b augmente..
On fixe la capacité et on fait varier le nombre d'objets
| n | Temps KP Dynamic (s) |
|---|---|
| 5 | 0.004 |
| 20 | 0.015 |
| 25 | 0.018 |
| 50 | 0.036 |
| 70 | 0.05 |
| 90 | 0.064 |
| 100 | 0.069 |
Le temps croisse avec
Avant de lancer la programmation dynamique, on peut réduire la taille du problème en fixant certaines variables à 0 ou 1 de façon certaine. La condition de fixation repose sur l'écart
Pour chaque variable
où
Le problème réduit
Sur l'instance de référence (n = 12, b = 53) :
- Solution gloutonne :
$z(\tilde{x}) = 78$ - Relaxation linéaire :
$\bar{z} = 80$ - Écart :
$\bar{z} - z(\tilde{x}) = 2$
Solution x (preprocessing) = [ 1 1 1 1 1 1 0 0 1 0 0 0 ]
Poids total = 52 (capacité 53)
Valeur totale = 78
La solution avec preprocessing est identique à celle de la DP classique, ce qui confirme que les variables ont été correctement fixées.
Le preprocessing réduit le problème dès lors que l'écart
A contrario, si le glouton donne une solution très éloignée de la borne LP (grand écart), peu ou aucune variable ne sera fixée et le preprocessing n'apportera rien.
Sur l'instance de référence (n = 12) :
- Variables fixées à 1 : x1, x2, x3 → 3 variables
- Variables fixées à 0 : x10, x11, x12 → 3 variables
- Variables libres pour la DP : x4, x5, x6, x7, x8, x9 → 6 variables
Soit 50 % des variables fixées, et le sous-problème transmis à la DP est de taille
La programmation dynamique a une complexité en
Le sous-problème est environ 3,7 fois plus petit que le problème d'origine. Sur de grandes instances, ce gain devient très significatif car la DP peut devenir prohibitive sans preprocessing.
En pratique, le coût du preprocessing lui-même est en



