Skip to content

About

Problème du sac à dos unidimensionnel. Travaux pratiques de la matière Modélisation et Optimisation des Systèmes Complexes

Topics

Resources

Stars

1 star

Watchers

0 watching

Forks

Latest commit

 

History

62 Commits

Folders and files

NameName
Last commit message
Last commit date
 
 
 
 
 
 
 
 
 
 

Repository files navigation

TPs : Modélisation et Optimisation des Systèmes Complexes

Lien du Repo GitHub

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

Introduction

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.


Rappel : problème du sac à dos (0/1)

On dispose de $n$ objets, chacun caractérisé par un poids $a_j$ et un profit $c_j$, ainsi que d'un sac de capacité $b$. On cherche à maximiser le profit total en choisissant quels objets emporter, sans dépasser la capacité :

$$ \max \sum_{j=1}^{n} c_j x_j \quad \text{s.c.} \quad \sum_{j=1}^{n} a_j x_j \leq b, \quad x_j \in {0,1} $$


TP1 : Relaxation Linéaire & Heuristique Gloutonne


Question 1 — Génération aléatoire des objets

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

Question 2 — Relaxation Linéaire (KP_LP)

La relaxation linéaire remplace la contrainte d'intégrité $x_j \in {0,1}$ par $x_j \in [0,1]$, autorisant la prise de fractions d'objets. On résout en triant par ratio $c_j / a_j$ décroissant et en remplissant le sac jusqu'à saturation.

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é : $O(n \log n)$ (dominée par le tri).


Question 3 — Heuristique Gloutonne (KP_greedy)

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é : $O(n \log n)$.


Question 4 — Comparaison des temps d'exécution

Partie A — n fixé, b variable

On fixe le nombre d'objets et on fait varier la capacité $b$.

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

Temps d'exécution — n fixé, b variable

Les deux algorithmes ont une complexité en $O(n \log n)$, indépendante de $b$. On observe que les temps restent quasi-constants quelle que soit la valeur de $b$, ce qui est cohérent : la capacité du sac n'intervient pas dans la complexité asymptotique, seul $n$ compte. Les légères variations sont dues au bruit de mesure.

Partie B — b fixé, n variable

On fixe la capacité et on fait varier le nombre d'objets $n$.

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

Temps d'exécution — b fixé, n variable

Les temps croissent avec $n$, ce qui confirme la dépendance en $O(n \log n)$. Le greedy est systématiquement un peu plus rapide que la LP car il évite de calculer une fraction : il s'arrête dès qu'un objet ne rentre pas, là où la LP calcule toujours la fraction résiduelle. L'écart reste faible car les deux algorithmes partagent la même structure de tri.


TP2 : Programmation Dynamique

Question 2 — Programmation Dynamique (KP_dynamic)

La programmation dynamique résout le problème de manière exacte en construisant un tableau $Z$ de taille $b+1$, où $Z[w]$ représente la valeur optimale pour une capacité $w$, et $D[w]$ l'index de l'objet pris à chaque étape (pour reconstruire la solution).

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é : $O(n \cdot b)$ en temps et en espace.


Question 3 — Comparaison des temps d'exécution

Partie A — n fixé, b variable

On fixe le nombre d'objets et on fait varier la capacité $b$.

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

Temps d'exécution — n fixé, b variable

L'algorithme a une compléxité de $O(n \cdot b)$ et on remarque que le temps tend à augmenter au fur et à mesure que la valeur b augmente..

Partie B — b fixé, n variable

On fixe la capacité et on fait varier le nombre d'objets $n$.

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

Temps d'exécution — b fixé, n variable

Le temps croisse avec $n$, ce qui confirme la dépendance en $O(n \cdot b)$.


TP3 : Réduction / Preprocessing de Variables

Principe

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 $\bar{z} - z(\tilde{x})$ entre la valeur de la relaxation linéaire $\bar{z}$ et la valeur de la solution gloutonne $z(\tilde{x})$.

Pour chaque variable $j$, on calcule :

$$ \bar{c}_j = \left| c_j - \frac{c_p}{a_p} \cdot a_j \right| $$

où $p$ est l'indice de l'objet critique (le premier objet qui ne rentre pas dans le sac lors du tri par ratio). Si $\bar{c}_j \geq \bar{z} - z(\tilde{x})$, alors la variable peut être fixée : à 1 si $j < p$, à 0 si $j > p$.

Le problème réduit $P_R$ ne contient que les variables non fixées, et c'est sur ce problème réduit qu'on applique la programmation dynamique.


Résultats sur instance3.csv

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.


Analyse de l'amélioration

1. Proportion de problèmes réduits

Le preprocessing réduit le problème dès lors que l'écart $\bar{z} - z(\tilde{x})$ est suffisamment petit par rapport aux $\bar{c}_j$ des objets extrêmes. Sur notre instance, l'écart vaut 2, ce qui est faible : presque toutes les variables situées loin de l'objet critique vérifient la condition. Le problème est donc réduit dans la grande majorité des cas lorsque la solution gloutonne est proche de l'optimum LP.

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.

2. Pourcentage de variables fixées

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 $n_R = 6$ au lieu de $n = 12$. Plus l'instance est grande et plus la solution gloutonne est bonne, plus ce pourcentage peut croître.

3. Gain de temps dans la résolution

La programmation dynamique a une complexité en $O(n \cdot b)$. En réduisant $n$ de moitié ($n_R = 6$ au lieu de 12) et en réduisant la capacité effective ($b_R = 29$ au lieu de 53 après déduction des objets fixés à 1), le gain théorique est :

$$ \frac{n \cdot b}{n_R \cdot b_R} = \frac{12 \times 53}{6 \times 29} \approx 3{,}7 $$

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 $O(n \log n)$ (dominé par le tri), ce qui est négligeable devant $O(n \cdot b)$ pour des instances de taille raisonnable.


About

Problème du sac à dos unidimensionnel. Travaux pratiques de la matière Modélisation et Optimisation des Systèmes Complexes

Topics

Resources

Stars

1 star

Watchers

0 watching

Forks

Contributors

Languages