En algorithmique, le problème du sac à dos, parfois noté (KP) (de l'anglais ) est un problème d'optimisation combinatoire. Ce problème classique en informatique et en mathématiques modélise une situation analogue au remplissage d'un sac à dos. Il consiste à trouver la combinaison d'éléments la plus précieuse à inclure dans un sac à dos, étant donné un ensemble d'éléments décrits par leurs poids et valeurs.
L'objectif du problème du sac à dos est de sélectionner des objets à mettre dans le sac à dos de façon à maximiser la somme des valeurs des objets pris, sous la contrainte que le poids total des objets pris ne dépasse pas la capacité du sac à dos. Ce problème est NP-complet. Ainsi, il est difficile à résoudre, en particulier pour les grands ensembles d'objets.
Pour résoudre le problème du sac à dos, il existe plusieurs algorithmes et approches différentes, notamment la programmation dynamique, les algorithmes gloutons et la programmation en nombres entiers. Ces algorithmes peuvent être appliqués à un large éventail de problèmes réels, tels que préparer une valise pour un voyage, allouer des ressources dans une chaîne d'approvisionnement et optimiser la gestion des stocks.
Histoire
Dans la recherche Le problème du sac à dos est l'un des 21 problèmes NP-complets de Richard Karp, exposés dans son article de 1972. Il est intensivement étudié depuis le milieu du et on trouve des références dès 1897, dans un article de .. La formulation du problème est fort simple, mais sa résolution est plus complexe. Les algorithmes existants peuvent résoudre des instances pratiques de taille importante. Cependant, la structure singulière du problème, et le fait qu'il soit présent en tant que sous-problème d'autres problèmes plus généraux, en font un sujet de choix pour la recherche.
Complexité et cryptographie Ce problème est à la base du premier algorithme de chiffrement asymétrique (ou à « clé publique ») présenté par Martin Hellman, Ralph Merkle et Whitfield Diffie à l'université Stanford en 1976 , dans la partie « » d'un projet de "" à l'université Stanford. La publication correspondante est : R.C. Merkle et M.E. Hellman, , , université Cornell, Ithaca, New York, octobre 1977.. Toutefois, même si l'idée est due au problème du sac à dos (dont l'algorithme porte le nom) , il est considéré comme le premier véritable algorithme de chiffrement asymétrique juste avant RSA publié l'année suivante.
La version NP-difficile de ce problème a été utilisée dans des primitives et des protocoles de cryptographie, tels que le cryptosystème de Merkle-Hellman. ou le cryptosystème de Chor-Rivest. Leur avantage par rapport aux cryptosystèmes asymétriques fondés sur la difficulté de factoriser est leur rapidité de chiffrement et de déchiffrement. Cependant, l'algorithme de Hellman, Merkle et Diffie est sujet aux « portes dérobées » algorithmiques, ce qui implique qu'il est « cassé », c'est-à-dire cryptanalysé A. Shamir, , , Vol. IT-30, , 1984. (Première publication en avril 1982.). Le problème du sac à dos est un exemple classique de méprise en ce qui concerne les liens entre la NP-complétude et la cryptographie. Une version revue de l'algorithme, avec une itération du problème du sac à dos, a alors été présentée, pour être sitôt cassée , « », département de mathématiques de l'université d'État de l'Ohio,v1985, vol. 1, .. Les algorithmes de chiffrement asymétrique fondés sur le sac à dos ont tous été cassés à ce jour, le dernier en date étant celui de Chor-Rivest S. Vaudenay, ..
Autres domaines concernés On l'utilise aussi pour modéliser les situations suivantes, quelquefois en tant que sous-problème : dans des systèmes d'aide à la gestion de portefeuille : pour équilibrer sélectivité et diversification dans le but de trouver le meilleur rapport entre rendement et risque pour un capital placé sur plusieurs actifs financiers (actions...) ; dans le chargement de bateau ou d'avion : tous les bagages à destination doivent être amenés, sans être en surcharge ; ou l’optimisation d’un navire de charge (cargo polyvalent ou porte-conteneurs) en fonction de plusieurs critères : poids, volume, destination, marchandises spécifiques (dangereuses ou frigorifiques), importance des clients…etc ; dans la découpe de matériaux : pour minimiser les chutes lors de la découpe de sections de longueurs diverses dans des barres en fer, de rouleaux de papier ou de textile etc.Voir par exemple .
Une autre raison de s'intéresser à ce problème est son apparition dans certaines utilisations de méthodes de génération de colonnes (ainsi pour le problème de « »).
Anecdotiquement et justifiant ainsi le nom du problème, un randonneur y est confronté au moment de préparer son périple : le sac à dos a une capacité limitée et il faut donc trancher entre prendre, par exemple, deux boîtes de conserve et une gourde de cinquante centilitres ou une seule boîte de conserve et une gourde d'un litre.
Énoncé mathématique Les données du problème peuvent être exprimées en termes mathématiques. Les objets sont numérotés par l'indice variant de 1 à . Les nombres et représentent respectivement le poids et la valeur de l'objet numéro . La capacité du sac sera notée .
Il existe de multiples façons de remplir le sac à dos. Pour décrire l'une d'elles il faut indiquer pour chaque élément s'il est pris ou non. On peut utiliser un codage binaire : l'état du -ème élément vaudra si l'élément est mis dans le sac, ou s'il est laissé de côté. Une façon de remplir le sac est donc complètement décrite par un vecteur, appelé vecteur contenu, ou simplement contenu : ; et le poids associé, ainsi que la valeur associée, à ce remplissage, peuvent alors être exprimés comme fonction du vecteur contenu.
Pour un contenu donné, la valeur totale contenue dans le sac est naturellement :
De même, la somme des poids des objets choisis est :
Le problème peut alors être reformulé comme la recherche d'un vecteur contenu (les composantes valant 0 ou 1), réalisant le maximum de la fonction valeur totale , sous la contrainte : (1) C'est-à-dire que la somme des poids des objets choisis ne dépasse pas la capacité du sac à dos.
En général, on ajoute les contraintes suivantes afin d'éviter les cas singuliers : : on ne peut pas mettre tous les objets ; : aucun objet n'est plus lourd que ce que le sac peut porter ; : tout objet a une valeur et apporte un gain ; : tout objet a un certain poids et consomme des ressources.
Terminologie : est appelée fonction objectif ; tout vecteur vérifiant la contrainte (1) est dit réalisable ; si la valeur de est maximale, alors est dit optimal.
NP-complétude Le problème du sac à dos peut être représenté sous une forme décisionnelle en remplaçant la maximisation par la question suivante : un nombre étant donné, existe-t-il une valeur des pour laquelle , avec respect de la contrainte ? Sous sa forme décisionnelle, lorsque les nombres sont représentés en notation binaire, le problème est NP-complet, ce qui signifie que l'on ne connaît pas de méthode générale pour construire une solution optimale, à part l'examen systématique de toutes les solutions envisageables. Le problème d'optimisation est NP-difficile, sa résolution est au moins aussi difficile que celle du problème de décision, et il n'existe pas d'algorithme polynomial connu (polynomial en le nombre de chiffres pour décrire une instance) qui, étant donné une solution, peut dire si elle est optimale (ce qui reviendrait à dire qu'il n'existe pas de solution avec un plus grand, donc à résoudre le problème de décision NP-complet).
Il y a un lien entre la version « décision » et la version « optimisation » du problème dans la mesure où s'il existe un algorithme polynomial qui résout la version « décision », alors on peut trouver la valeur maximale pour le problème d'optimisation de manière polynomiale en effectuant de la dichotomie pour trouver entre 1 et et en appelant l'algorithme polynomial qui résout la version « décision » (attention, si on parcourt toutes les valeurs de de 1 à on obtiendrait un algorithme exponentiel en la taille de l'instance). D'autre part, si un algorithme trouve la valeur optimale du problème d'optimisation en un temps polynomial, alors le problème de décision peut être résolu en temps polynomial en comparant la valeur de la solution sortie par cet algorithme avec la valeur de . Ainsi, les deux versions du problème sont de difficulté similaire.
Procédé d'exploration systématique
Un examen systématique peut être réalisé à l'aide d'un arbre d'exploration binaire tel celui représenté ci-contre (les triangles représentent des sous-arbres).
L'arbre se décrit en descendant depuis le sommet jusqu'au bas des triangles (les feuilles de l'arbre). Chaque case correspond à un unique parcours possible. En suivant les indications portées le long des arêtes de l'arbre, à chaque parcours correspond une suite de valeurs pour formant un vecteur contenu. Il est alors possible de reporter dans chaque case la valeur totale et le poids total du contenu correspondant. Il ne reste plus qu'à éliminer les cases qui ne satisfont pas la contrainte, et à choisir parmi celles qui restent celle (ou une de celles) qui donne la plus grande valeur à la fonction objectif.
À chaque fois qu'un objet est ajouté à la liste des objets disponibles, un niveau s'ajoute à l'arbre d'exploration binaire, et le nombre de cases est multiplié par 2. L'exploration de l'arbre et le remplissage des cases ont donc un coût qui croît exponentiellement avec le nombre d'objets.
Preuve de la NP-complétude
Cette preuve de NP-complétude a été présentée par Michail G. Lagoudakis Michail G. Lagoudakis, , 1996. reprenant un article de Richard Karp et un article de J.E. Savage.
Résolution approchée
Comme pour la plupart des problèmes NP-complets, il peut être intéressant de trouver des solutions réalisables mais non optimales. De préférence avec une garantie sur l'écart entre la valeur de la solution trouvée et la valeur de la solution optimale.
On appelle efficacité d'un objet le rapport de sa valeur sur son poids. Plus la valeur de l'objet est importante par rapport à ce qu'il consomme, plus l'objet est efficace.
Algorithme glouton L'algorithme le plus simple est un algorithme glouton. L'idée est d'ajouter en priorité les objets les plus efficaces, c'est-à-dire ceux qui maximisent le profit sur la place occupée , jusqu'à saturation du sac :
trier les objets par ordre décroissant d'efficacité w_conso := 0
pour i de 1 à n si w[i] + w_conso ≤ W alors x[i] := 1 w_conso := w_conso + w[i] sinon x[i] := 0 fin si fin pour
Analyse de l'algorithme glouton On notera la valeur des solutions optimales.
La solution retournée par l'algorithme glouton peut être d'aussi mauvaise qualité que possible. Considérons par exemple que nous n'ayons que deux objets à placer dans le sac. Le premier a un profit de 2 et un poids de 1, le deuxième a un profit et un poids tous deux égaux à . Le premier objet est le plus efficace, il sera choisi en premier et empêchera la prise du second, donnant ainsi une solution de valeur 2 alors que la solution optimale vaut . Il existe donc des valeurs du problème pour lesquelles le rapport entre la solution trouvée et la solution optimale est aussi proche de zéro que possible.
Il existe d'autres algorithmes d'approximation pour le problème de sac à dos permettant d'avoir une solution garantie à une distance ou à un rapport de la qualité de solution optimale. C’est-à-dire que la solution trouvée est telle que ou . La complexité en temps de ces algorithmes est, en général, fonction de l'inverse de la qualité attendue ; par exemple ou . Dans le second cas, cela fournit un schéma d'approximation en temps entièrement polynomial.
Métaheuristiques