Le problème du sac à dos

Le problème du sac à dos est un classique de l’optimisation combinatoire qui intéresse toute personne souhaitant maximiser la valeur d’un ensemble d’objets soumis à une contrainte de poids. Cet article s’adresse aux étudiants en informatique, mathématiques appliquées ou ingénierie qui découvrent ce problème et souhaitent comprendre ses enjeux, ses méthodes de résolution et ses implications pratiques.

La question

Le problème du sac à dos consiste à déterminer quels objets choisir parmi un ensemble donné, chacun ayant un poids et une valeur, pour remplir un sac dont la capacité maximale en poids est limitée, de manière à maximiser la valeur totale des objets sélectionnés sans dépasser cette limite. Ce problème est important car il modélise de nombreuses situations réelles où il faut faire des choix optimaux sous contraintes, par exemple en logistique, finance ou planification.

Concepts de base

Pour formaliser ce problème, on considère :

• Un sac à dos avec une capacité maximale en poids notée P.
• Un ensemble de n objets, chacun identifié par un indice i allant de 1 à n.
• Chaque objet i possède un poids pi et une valeur vi.

La décision à prendre est représentée par une variable binaire xi associée à chaque objet i :

• xi = 1 si l’objet i est choisi et mis dans le sac,
• xi = 0 sinon.

La contrainte principale est que la somme des poids des objets sélectionnés ne dépasse pas la capacité :

∑(i=1 à n) xi.pi ≤ P

L’objectif est de maximiser la valeur totale des objets choisis :

max ∑(i=1 à n) xi.vi

Une solution est dite réalisable si elle respecte la contrainte de poids, et optimale si elle maximise la valeur totale parmi toutes les solutions réalisables.

Par exemple, avec quatre objets et un sac de capacité 30 kg, une solution réalisable peut être de choisir les objets 2, 3 et 4, mais cette solution n’est pas optimale si une autre combinaison donne une valeur totale plus élevée sans dépasser le poids maximal.

Approche

Deux grandes catégories de méthodes permettent de résoudre ce problème :

• Les méthodes approchées (heuristiques) qui fournissent rapidement une solution proche de l’optimale, mais sans garantie d’optimalité.
• Les méthodes exactes qui garantissent de trouver la solution optimale, mais peuvent être coûteuses en temps de calcul, surtout pour de grands ensembles.

Méthode approchée : algorithme glouton

Cette méthode consiste à calculer pour chaque objet le rapport valeur/poids (vi/pi), puis à trier les objets par ordre décroissant de ce rapport. Ensuite, on ajoute les objets un par un dans le sac tant que la contrainte de poids est respectée.

Exemple avec quatre objets :

• Calcul des rapports : 0,54, 0,33, 0,37, 0,30
• Tri décroissant : objets 1, 3, 2, 4
• Ajout dans le sac : objet 1 (poids 13), objet 3 (poids 8), puis on ne peut pas ajouter objet 2 (poids total dépasserait 30), ni objet 4.

La solution obtenue est donc les objets 1 et 3, d’une valeur totale de 10. Cette solution n’est pas optimale, mais la méthode est rapide et efficace lorsque le nombre d’objets augmente.

Cette approche est dite « gloutonne » car elle ne revient jamais sur une décision prise précédemment, même si une meilleure solution pourrait être obtenue en remplaçant certains objets.

Méthode exacte : procédure par séparation et évaluation (PSE)

La PSE, ou « branch and bound », explore intelligemment l’ensemble des solutions possibles en construisant un arbre de recherche :

• Chaque nœud représente une étape où certains objets sont choisis ou exclus.
• Chaque branche correspond à la décision d’inclure ou non un objet.

Les feuilles de l’arbre correspondent à des solutions complètes, mais certaines peuvent être irréalisables (poids dépassant la capacité). L’algorithme calcule la valeur de chaque solution réalisable et retient la meilleure.

Pour limiter l’explosion combinatoire (l’arbre a une taille exponentielle en n), la PSE utilise des bornes :

• Borne inférieure : valeur minimale garantie d’une solution réalisable, par exemple obtenue par une heuristique.
• Borne supérieure : valeur maximale possible à partir d’un nœud, calculée en additionnant la valeur des objets déjà choisis et une estimation optimiste des objets restants.

Si la borne supérieure d’un nœud est inférieure à la borne inférieure actuelle, on peut « couper » cette branche, car elle ne mènera pas à une meilleure solution.

Cette technique permet d’élaguer l’arbre et d’accélérer la recherche de la solution optimale. Par exemple, dans l’exemple donné, la solution optimale peut être trouvée en explorant seulement 9 nœuds au lieu de 31.

Résultats

Les méthodes approchées fournissent rapidement des solutions réalisables, mais pas nécessairement optimales. L’algorithme glouton présenté donne une solution correcte en un temps réduit, même pour un grand nombre d’objets.

Les méthodes exactes, notamment la PSE, garantissent la solution optimale mais peuvent nécessiter un temps de calcul important. L’utilisation de bornes permet cependant de réduire considérablement le nombre de solutions à explorer.

La méthode itérative d’énumération des sous-ensembles, basée sur la correspondance entre les sous-ensembles et les entiers binaires, est simple mais devient rapidement inefficace lorsque le nombre d’objets augmente.

La méthode récursive explore l’arbre des solutions de manière similaire à la PSE mais sans optimisation, ce qui peut entraîner un grand nombre de calculs inutiles.

Limites et questions ouvertes

Le problème du sac à dos est connu pour sa complexité exponentielle, ce qui limite l’efficacité des méthodes exactes pour de très grands ensembles d’objets. Les heuristiques, bien que rapides, ne garantissent pas l’optimalité.

Les optimisations proposées, comme l’élagage dans la PSE, améliorent la performance mais ne suppriment pas complètement le problème de la croissance exponentielle.

Une question ouverte est de savoir comment intégrer des optimisations supplémentaires dans les méthodes récursives ou itératives pour réduire le temps de calcul sans perdre la garantie d’optimalité.

Glossaire

• Objet : élément avec un poids et une valeur à considérer pour inclusion dans le sac.
• Poids maximal (P) : capacité maximale en poids que le sac peut contenir.
• Variable binaire (xi) : indicateur de sélection d’un objet (1 = choisi, 0 = non choisi).
• Solution réalisable : sélection d’objets respectant la contrainte de poids.
• Solution optimale : solution réalisable avec la valeur totale maximale.
• Algorithme glouton : méthode approchée qui sélectionne les objets selon un critère local sans revenir en arrière.
• Procédure par séparation et évaluation (PSE) : méthode exacte utilisant un arbre de recherche et des bornes pour élaguer les solutions non prometteuses.
• Borne inférieure : estimation minimale de la meilleure valeur possible.
• Borne supérieure : estimation maximale de la meilleure valeur possible à partir d’un nœud donné.
• Élagage : suppression de branches de l’arbre de recherche qui ne peuvent pas conduire à une meilleure solution.