Problème du sac à dos - Définition

Variantes

Le problème présenté jusqu'ici est, plus précisément, le problème de sac à dos en variables binaires (01KP). Il s'agit en fait d'une variante parmi d'autres. Cette section présente ces différentes variantes. Les particularités se font sur le domaine des variables, le nombre de valeurs des objets, le nombre de dimensions du sac, etc. Ces particularités peuvent aussi être combinées.

Variables continues

Le problème du sac à dos en variables continues (LKP) est obtenu en enlevant la contrainte d'intégrité sur les variables. C’est-à-dire que l'on s'autorise à ne prendre qu'une fraction des objets dans le sac à dos : . Contrairement à KP, LKP appartient à la classe de complexité P.

Voici un algorithme permettant de calculer une solution optimale du problème LKP :

      trier les objets en ordre décroissant d'efficacité      i:= 1      w_dispo:= W            tant que w_dispo >= w[i] faire        x[i]:= 1        w_dispo:= w_dispo - w[i]        i:= i + 1      fin tant que            x[i]:= w_dispo / w[i]            tant que i < n faire        i:= i + 1        x[i]:= 0      fin tant que      

On remarquera que la valeur de la solution optimale de LKP est au plus égale au double de la valeur de la solution optimale du problème KP correspondant :

Variables entières

Dans le problème de sac à dos en variables entières, on considère que l'on a plusieurs exemplaires de chaque objet. Le problème consiste donc à trouver le nombre d'exemplaires à prendre pour chacun.

Si le nombre d'exemplaires est limité, on parlera de sac à dos borné (BKP), sinon on parlera de sac à dos non borné (UKP). Le problème BKP peut être transformé en 01KP sans difficulté.

Sac à dos multidimensionnel

On considère ici que le sac à dos a d dimensions, avec d > 0 (d-KP). Par exemple, on peut imaginer une boîte. Chaque objet a trois dimensions, et il ne faut déborder sur aucune des dimensions. La contrainte (1) est alors remplacée par :

• 

Utilisation pratique

En pratique, la version multidimensionnelle peut servir à modéliser et résoudre le problème du remplissage d'un container dont le volume et la charge maximale sont limitées.

Un autre exemple est celui de la gestion de personnel. Dans une version simplifiée, on estime la productivité ou la compétence de chaque personne (son « poids » dans le problème), et on lui attribue d'autres variables : son coût et sa disponibilité. Chacun de ces paramètres représente une dimension du sac à dos. On définit finalement les contraintes liées à son projet eu égard les paramètres précédents : le budget disponible et le temps imparti pour réaliser le travail. La résolution permet de déterminer quelles personnes doivent être retenues pour réaliser le projet.

Sac à dos multi-objectif

Une variante du problème consiste, à partir d'objets ayant plusieurs valeurs, à maximiser plusieurs fonctions objectifs, c'est le problème du sac à dos multi-objectif (MOKP). On rentre donc dans le domaine de l'optimisation multi-objectif.

Par exemple, supposons que vous lanciez une société spécialisée dans les croisières. Pour vous faire connaître, vous décidez d'inviter des gens célèbres à bord de votre plus beau bateau. Ce bateau ne peut supporter plus d'une tonne de passagers (ce sera la constante W). Chaque passager a une masse (w), vous apporte de la publicité par sa popularité (p¹ : indice de popularité) et vous demande un salaire (p² : salaire négatif). Vous voulez, bien sûr, maximiser la publicité apportée et minimiser le salaire total à payer (maximiser le salaire négatif). De plus vous voulez avoir un maximum de gens sur votre bateau (p³ = 1). Vous avez donc trois sommes à maximiser.

En termes mathématiques, vous cherchez le vecteur X de gens célèbres satisfaisant le problème :

• max  : on veut une popularité maximale ;
• max  : minimiser le salaire à payer (maximiser le salaire négatif) ;
• max  : et avoir un maximum de gens sur le bateau

sous contraintes

•  : le bateau ne doit pas couler.

D'une manière générale, on remplace la fonction objectif du problème initial par une famille de fonctions objectifs :

• max

Sac à dos quadratique

Le problème de sac à dos quadratique est noté QKP. On a ici un gain g_ij supplémentaire lorsque deux objets (i et j) sont pris simultanément. Par exemple, disons que vous souhaitiez maximiser la qualité de votre café lors d'une expédition avec un sac à dos. On peut comprendre qu'il est plus intéressant d'apporter une cuillère et un sucre plutôt qu'un seul des deux.

La fonction objectif s'écrit alors :

• max

Problème de la somme de sous-ensembles ou du subset sum

La particularité du problème de la somme de sous-ensembles (en anglais : subset sum) est que la valeur et le poids des objets sont identiques (p_i = w_i). C'est un problème important du domaine de la cryptographie, utilisé dans plusieurs systèmes de génération de clé publique.

Sac à dos à choix multiple

Dans le problème de sac à dos à choix multiple (MCKP), les objets sont regroupés en classes, et il ne faut prendre qu'un seul représentant pour chaque classe.

Par exemple, vous êtes en train de confectionner votre boîte à outils. Si vous avez cinq clés à molette. Vous pouvez soit choisir la plus légère, afin de prendre un marteau performant, ou alors choisir la clé la plus performante et un marteau bas de gamme, ou alors faire un compromis. L'idée générale est que vous ne pouvez pas prendre plus d'une clé, ni plus d'un marteau.

Si les objets sont rangés en k classes, on notera l'ensemble des indices des objets appartenant à la classe j. On considère, bien entendu, qu'un objet n'appartient qu'à une unique classe. La formulation du problème devient :

• max

sous contraintes :

•  : on ne dépasse pas la capacité du sac ;
•  : on choisit au plus un représentant de chaque classe.

Sac à dos multiple

Le problème de sac à dos multiple (MKP) consiste à répartir un ensemble d'objets dans plusieurs sacs à dos de capacités différentes. La valeur d'un objet dépend maintenant du sac dans lequel il est placé. Par exemple, on peut considérer qu'un euro a plus de valeur sur un compte d'épargne que sur un compte courant.

Si on a k sacs à dos, on notera si l'objet i est placé dans le sac j. La formulation du problème devient :

• max

sous contraintes

•  : on ne dépasse pas la capacité des sacs ;
•  : un objet n'est mis que dans un sac.

Il existe une variante de ce problème dans laquelle tous les sacs ont la même capacité, on le note MKP-I.