Étude

Le problème du sac à dos est un problème fondamental en algorithmie, nombre de problèmes courant pouvant se modéliser sous cette forme.

Sac à dos fractionnel

Commençons par une version simplifiée du problème, dit du sac à dos fractionnel :

Par exemple, on a un sac à dos de 20kg et six poudres de paramètres :

• poudre 1 : 15kg et un prix de 135€ (9€ le kilo)
• poudre 2 : 2kg et un prix de 30€ (15€ le kilo)
• poudre 3 : 4kg et un prix de 32€ (8€ le kilo)
• poudre 4 : 1kg et un prix de 6€ (6€ le kilo)
• poudre 5 : 6kg et un prix de 18€ (3€ le kilo)
• poudre 6 : 80kg et un prix de 800€ (10€ le kilo).

Le sac peut contenir soit :

• 20kg de la poudre 6, pour un profit de 200€,
• 14kg de la poudre 1 et 6kg de la poudre 5, pour un profit de 114€,
• 1kg de la poudre 1 à 5 et le reste (15kg) en poudre 6, pour un profit de 192€,
• ...

Résolution par un algorithme glouton

Un algorithme "glouton" ajoute itérativement un élément à une solution possible pour rendre au final une solution la plus grande possible. Dans le cas du sac à dos, on ajoute petit à petit des produit jusqu'à ce que le sac soit plein. Reste à choisir l'ordre dans lequel ajouter les poudre et comme on veut maximiser le profit, on choisi de prendre les poudres par prix au kilo décroissant.

On obtient donc in fine l'algorithme suivant, écrit en python :

def glouton(produits, masse_totale):
    ordre = list(range(len(produits)))
    ordre.sort(key=lambda i: -produits[i]["prix"] / produits[i]["kg"])

    sac_a_dos = [0] * len(produits)

    for i in ordre:
        x = produits[i]
        if masse_totale >= x["kg"]:
            sac_a_dos[i] = 1
            masse_totale -= x["kg"]
        elif masse_totale > 0:
            sac_a_dos[i] = masse_totale / x["kg"]
            masse_totale = 0
        else:
            break

    return sac_a_dos

• entrée : une liste de produits, où chaque produit est un dictionnaire contenant les clés "prix" et "kg"
• sortie : une liste tel que l'élément d'indice i contienne la fraction de poudre (entre 0 et 1) du produit d'indice i dans le sac à dos.

La complexité de cet algorithme est déterminée par le tri, puisque l'intérieure de la boucle for est en temps constant.

Testons cet algorithme sur l'exemple. Si on devait coder les données de l'exemple, on aurait quelque chose du genre :

EXEMPLE = [
    {
        "nom": "poudre 1",
        "kg": 15,
        "prix": 135,
    },
    {
        "nom": "poudre 2",
        "kg": 2,
        "prix": 30,
    },
    {
        "nom": "poudre 3",
        "kg": 4,
        "prix": 32,
    },
    {
        "nom": "poudre 4",
        "kg": 1,
        "prix": 6,
    },
    {
        "nom": "poudre 5",
        "kg": 6,
        "prix": 18,
    },
    {
        "nom": "poudre 6",
        "kg": 80,
        "prix": 800,
    },
]

Notez que l'on a ajouté une clé "nom" pour retrouver l'objet dans le sac à dos.

Remarquez que l'algorithme prendra toujours toute la poudre disponible à part peut-être la dernière.

Cet algorithme glouton est même optimal !

Problème du sac à dos

Le fait de pouvoir fractionner les éléments est un cas particulier heureux, mais ce n'est pas la norme, pensez à un déménagement : les déménageurs ne peuvent prendre qu'un bout du canapé sous prétexte qu'il ne rentre pas en entier dans le camion... La formalisation classique du sac à dos ne permet pas de scinder des objets :

Ce problème se décline de plein de façons pratique :

• en remplaçant le prix par la quantité nutritive et maximiser un road trip
• en remplaçant la masse par le volume on peut remplir un camion de déménagement au maximum théorique
• mais aussi le stockage de fichiers (les produits) sur un disque dur (le sac à dos) de capacité limité (le prix est la taille de chaque fichier)
• ou encore maximiser la charge d'un générateur
• ...

Comme on ne peut pas découper les produits au contraire du sac à dos fractionnel, on a le résultat suivant :

Algorithme glouton

Comme les solutions du sac à dos sont des solutions admissible du sac à dos fractionnel, on peut tenter d'adapter l'algorithme glouton (optimal) précédent au problème du sac à dos :

def glouton(produits, masse_totale):
    ordre = list(range(len(produits)))
    ordre.sort(key=lambda i: -produits[i]["prix"] / produits[i]["kg"])

    sac_a_dos = [0] * len(produits)

    for i in ordre:
        x = produits[i]
        if masse_totale >= x["kg"]:
            sac_a_dos[i] = 1
            masse_totale -= x["kg"]

    return sac_a_dos

• entrée : une liste de produits, où chaque produit est un dictionnaire contenant les clés "prix" et "kg"
• sortie : une liste tel que l'élément d'indice i contienne la fraction de poudre (entre 0 et 1) du produit d'indice i dans le sac à dos.

Reprenons l'exemple et modifions le pour que l'on ne puisse pas prendre une fraction de poudre :

• poudre 1 : 15kg et un prix de 135€ (9€ le kilo)
• poudre 2 : 2kg et un prix de 30€ (15€ le kilo)
• poudre 3 : 4kg et un prix de 32€ (8€ le kilo)
• poudre 4 : 1kg et un prix de 6€ (6€ le kilo)
• poudre 5 : 6kg et un prix de 18€ (3€ le kilo)
• poudre 6 : 80kg et un prix de 800€ (10€ le kilo). On supprime ce produit puisqu'il ne rentre pas dans le sac.

En maximisant le profit, l'algorithme glouton préconise de prendre les poudres 1, 2 et 4 pour un profit de 171€. On se rend cependant compte que cette solution n'est plus maximale ! En effet prendre les poudres 1, 3 et 4 rapporte un profit de 173€.

On peut même montrer que l'algorithme glouton ne possède pas de garantie :

On peu alors vouloir modifier l'algorithme glouton pour considérer le prix total et pas celui au kilo (on trouve alors l'optimum pour l'exemple) mais ce n'est pas non plus super :

Tout n'est cependant pas perdu car on peut modifier l'algorithme glouton pour qu'il soit à performance garantie.

Algorithme à performance garantie

Lors de l'exécution de l'algorithme glouton, soit $i^\star$ la dernière étape, qui est la seule pour laquelle le produit ne peut pas être ajouté dans le sac. On a alors :

• $\sum_{i < i^\star} k_i \leq K$
• $\sum_{i < i^\star} k_i + k_{i^\star} > K$
• la solution du sac à dos fractionnel associé est : $\sum_{i < i^\star} p_i + (\frac{K-\sum_{i < i^\star} k_i}{k_{i^\star}}) \cdot p_{i^\star}$

Des constatations ci-dessus on peut alors constituer l'algorithme suivant (en supposant sans perte de généralité que $k_i \leq K$ pour tout $i$ donc que tous les produits rentrent dans le sac) :

1. on trie tous les produits par prix au kilo décroissante
2. on note $i^\star$ le premier élément dans cet ordre tel que $\sum_{i \leq i^\star} k_i > K$
3. l'algorithme rend $\max(\sum_{i < i^\star} p_i, p_{i^\star})$.

Cette simple modification permet de garantir la solution obtenue :

Solution par énumération

Pour trouver la solution maximale à un problème d'optimisation, on peut toujours énumérer toutes les solutions. Dans le cas d'un sac à dos cela revient à énumérer tous les sous ensembles de l'ensemble des produits et de prendre celui qui maximise le sac à dos. Pour aider à l'énumération, formalisons le problème du sac à dos sous la forme d'un problème d'optimisation linéaire en nombre entier :

Énumération exhaustive

Énumérer toutes les solutions possibles du sac à dos revient à choisir pour chaque $x_i$ s'il vaut 0 ou 1 puis de vérifier pour cette affectation :

• si elle est réalisable, c'est à dire que les produits choisis tiennent tous dans le sac à dos
• si la fonction objectif est maximale par rapport aux affectations déjà faite

Pour minimiser le temps pris pour faire cet algorithme il faut s'assurer de ne pas refaire une affectation déjà faite. On peut pour cela reprendre l'algorithme successeur qui permet de trouver le successeur d'un nombre écrit sous sa forme binaire.

L'algorithme peut alors être, avec des produits organisés comme l'EXEMPLE :

def énumération(produits, K):
    kg = [x["kg"] for x in produits]
    prix = [x["prix"] for x in produits]
    n = len(produits)

    sac_à_dos = [0] * n

    sac_à_dos_max = list(sac_à_dos)
    sac_à_dos_profit_max = 0

    while sac_à_dos != [1] * n:
        successeur(sac_à_dos)

        if sum(x * y for x, y in zip(sac_à_dos, kg)) <= K:
            profit = sum(x * y for x, y in zip(sac_à_dos, prix))
            if profit > sac_à_dos_profit_max:
                sac_à_dos_profit_max = profit
                sac_à_dos_max = list(sac_à_dos)

    return sac_à_dos_max

La complexité de l'algorithme est la somme de :

• la complexité totale de tous les appels à successeur et que l'on a déterminé (à de multiple reprise) dans la partie consacrée à la complexité amortie étant égale à $\mathcal{O}(2^n)$
• la complexité du calcul de la fonction objectif et de l'admissibilité ($\mathcal{O}(n)$ pour les 2 calculs) pour chaque affectation (il y en a $\mathcal{O}(n)$) : $\mathcal{O}(n \cdot 2^n)$
• le stockage de l'affectation ($\mathcal{O}(n)$) possiblement pour chaque affectation (il y en a $\mathcal{O}(n)$) : $\mathcal{O}(n \cdot 2^n)$

On obtient une complexité totale de $\mathcal{O}(n \cdot 2^n)$. La complexité est exponentielle, mais c'est du au fait qu'il y a beaucoup de cas à voir. L'analyse d'une affectation particulière est simple.

Branch and bound

La méthode du Branch and Bound (ou Séparation et évaluation en Français) est une méthode générale permettant d'accélérer la recherche de l'optimum d'un problème d'optimisation par recherche exhaustive si l'on peut trouver facilement une borne supérieure à un sous-problème où certaines affectation (mais pas toutes) ont déjà été faites.

Cette méthode est particulièrement bien adaptée au problème du sac à dos.

Bornes supérieure

On peut toujours considérer un problème de sac à dos comme un problème de sac à dos fractionnel que l'on peut facilement résoudre. Comme les solutions d'un sac à dos sont contenus dans les solution d'un sac à dos fractionnel (on prend pour chaque produit soit tout soit rien) on peut :

• majorer la solution du sac à dos par la valeur optimale du sac à dos fractionnel,
• si la solution du sac à dos fractionnel est aussi une solution du sac à dos alors c'est aussi la solution optimale du sac à dos.

Si l'on reprend l'exemple en supprimant la poudre 6 qui ne rentre pas en entier dans le sac, on obtient une solution du sac à dos fractionnel valant :

• 15kg de poudre 1 (l'entièreté)
• 2kg de poudre 2 (l'entièreté)
• 3/4 de la poudre 3

Pour un profit de 174€ qui est bien strictement plus grand que le profit max du sac à dos (qui vaut 173€). Remarquez que l'on ne peut pas déduire la solution entière à partir de la solution fractionnelle : elle contient la poudre 2 qui n'est pas dans la solution optimale.

Sous-problème

Si on fixe une variable pour un problème du sac à dos, on se ramène à un sac à dos plus petit :

On peut ainsi fixer n'importe quel sous-ensemble de variables et toujours avoir à résoudre un problème de sac à dos.

Une solution ouverte ne possédant que des -1 correspond au problème général du sac à dos et les solutions ouvertes ayant des 0 et des 1 correspondent à un sous-problème.

Déroulement de l'algorithme

L'algorithme du Branch and bound est alors très simple : il va énumérer toutes les solutions ouvertes mais ne va les explorer que si cela en vaut le coup, c'est à dire s'il est possible de trouver une solution meilleure que celle qu'on a déjà.

• initialisation : on commence avec un sac à dos vide et la solution ouverte ne contenant que des -1.
• tant que : il existe une solution ouverte non explorée, on calcule la valeur de son sac à dos fractionnel optimal.
  • Si cette valeur est inférieure à celle du sac à dos courant, il est inutile de l'explorer car on ne pourra trouver que des solutions moins bonnes.
  • Sinon :
    • si le sac à dos fractionnel optimal est un sac à dos on compare sa valeur au sac à dos stocké et on le met à jour si cette nouvelle solution est meilleure
    • sinon, il faut explorer de nouveaux sous-problème en fixant la valeur fractionnelle de la solution optimale à 0 et à 1. On ajoute ces deux sous problèmes aux solutions ouvertes à explorer.

Avant de formaliser tout ça, regardons ce que cela fait sur l'exemple. On a un sac à dos de $K=20$ et 5 produits :

• poudre 1 : 15kg et un prix de 135€ (9€ le kilo)
• poudre 2 : 2kg et un prix de 30€ (15€ le kilo)
• poudre 3 : 4kg et un prix de 32€ (8€ le kilo)
• poudre 4 : 1kg et un prix de 6€ (6€ le kilo)
• poudre 5 : 6kg et un prix de 18€ (3€ le kilo)
• poudre 6 : 80kg et un prix de 800€ (10€ le kilo)

On commence par la solution ouverte $y = [-1, -1, -1, -1, -1, -1]$ de solution fractionnelle optimale $[0, 1, 0, 0, 0, 0.225]$ et le sac à dos vide $x = [0, 0, 0, 0, 0, 0]$. On a coutume de représenter les différents choix par un arbre. Après cette étape d'initialisation on a :

Le sac à dos fractionnel n'est pas un sac à dos. On ajoute donc potentiellement les solutions ouvertes $[-1, -1, -1, -1, -1, 1]$ et $[-1, -1, -1, -1, -1, 0]$ aux solutions à explorer. Comme $[-1, -1, -1, -1, -1, 1]$ ne peut pas donner de sac à dos valide, on se retrouve avec les solutions ouvertes à explorer suivantes :

La solution à explorer est $[-1, -1, -1, -1, -1, 0]$ de solution fractionnelle optimale $[1, 1, 0.75, 0, 0, 0]$ et de valeur 189.0 qui est strictement supérieure à notre sac à dos stocké. On explore cette solution pour obtenir :

L'analyse de la solution ouverte $[-1, -1, 1, -1, -1, 0]$ donne une solution fractionnelle optimale de $[0.9333333333333333, 1, 1, 0, 0, 0]$ et de valeur 188, ce qui fait que l'on continue l'exploration :

L'analyse de la solution ouverte $[1, -1, 1, -1, -1, 0]$ donne une solution fractionnelle optimale de $[1, 0.5, 1, 0, 0, 0]$ et de valeur 182, ce qui fait que l'on continue encore :

Notez que la solution ouverte $[1, 1, 1, -1, -1, 0]$ de donne pas de sac à dos viable, elle est donc directement éliminée.

Lors de l'analyse de la solution ouverte $[1, 0, 1, -1, -1, 0]$, quelque chose de nouveau arrive : la solution fractionnelle optimale est un sac à dos ! Il contient $[1, 0, 1, 1, 0, 0]$ et vaut 173. On met à jour notre sac à dos et il est inutile de continuer cette voie. À l'issue de cette étape on a :

L'analyse de la solution ouverte $[0, -1, 1, -1, -1, 0]$ donne une solution optimale $[0, 1, 1, 1, 1, 0]$ de valeur 86 ce qui est moins bon que notre sac à dos stocké : inutile d'explorer. On a :

Remarquer que cette algorithme est bien plus efficace en pratique que l'énumération exhaustive, on a parcouru que que 11 des 32 sac à dos possibles.

Algorithme

On suppose que l'on possède l'algorithme borne_supérieure(ouverte, produits, masse_totale) qui à partir d'une solution ouverte le sac à dos fractionnel optimal. Pour notre exemple, on aurait ainsi que borne_supérieure([-1, -1, 1, -1, -1,-1], EXEMPLE, 20) vaudrait [0.933333, 1, 1, 0, 0, 0]

Il nous faut aussi deux fonctions utilitaires :

• première_valeur_fractionnelle(sac_à_dos_fractionnel) qui rend le plus petit indice tel que la valeur du tableau est strictement entre 0 et 1 ou None si un tel indice n'existe pas. Pour notre exemple, on aurait ainsi que : première_valeur_fractionnelle([1, 0.3, 1, 1, 0]) aurait rendu 1 et première_valeur_fractionnelle([1, 0, 1, 1, 0]) aurait rendu None
• profit(sac_à_dos_fractionnel, produits) qui rend le profit associé au sac à dos fractionnel passé en entrée

def branch_and_bound(produits, masse_totale):
    ordre = list(range(len(produits)))
    ordre.sort(key=lambda i: -produits[i]["prix"] / produits[i]["kg"])

    n = len(produits)

    sac_à_dos = [0] * n
    profit_sac_à_dos = 0

    solution_ouverte = [-1] * n
    solutions_ouvertes_possibles = [solution_ouverte]

    while solutions_ouvertes_possibles:
        solution_ouverte = solutions_ouvertes_possibles.pop()

        sac_à_dos_fractionnel = borne_supérieure(solution_ouverte, produits, masse_totale)
        profit_sac_à_dos_fractionnel = profit(sac_à_dos_fractionnel, produits)

        if profit_sac_à_dos_fractionnel > profit_sac_à_dos:
            i = première_valeur_fractionnelle(sac_à_dos_fractionnel)
            if i is None:
                sac_à_dos = sac_à_dos_fractionnel
                profit_sac_à_dos = profit_sac_à_dos_fractionnel
            else:
                for v in [0, 1]:
                    nouvelle_solution_ouverte = list(solution_ouverte)
                    nouvelle_solution_ouverte[i] = v
                    if (sum(x["kg"] for x, o in zip(produits, nouvelle_solution_ouverte) if o == 1) <= masse_totale):
                        solutions_ouvertes_possibles.append(nouvelle_solution_ouverte)
    return sac_à_dos

Si on a pas de chance, il faut explorer toutes les possibilités, la complexité est donc égale au nombre de solutions possible multiplié par la somme de la complexité des deux algorithmes gloutons. Dans notre cas $\mathcal{o}(2^n \cdot n \log(n))$. Notez que comme les deux algorithmes gloutons dépendent tous du même tri, on peut ne trier qu'une seule fois puis utiliser des algorithmes en $\mathcal{O}(n)$. La complexité totale est alors $\mathcal{O}(n \log(n) + 2^n \cdot n) = \mathcal{O}(2^n \cdot n)$, identique à la complexité de la recherche exhaustive.

Enfin, on peut accélérer l'algorithme en prenant comme valeur de départ le résultat de l'algorithme glouton.

Solution par programmation dynamique

Les sous problèmes associés au problème du sac à dos sont les même que pour le branch and bond ! En effet, soient $[p_1, \dots, p_n]$, $[k_1, \dots, k_n]$ et $K$ les données d'un problème du sac à dos et $V([p_1, \dots, p_n], [k_1, \dots, k_n], K)$ sa valeur optimale. Alors de deux choses l'une :

• soit la solution optimale contient le produit$x_n$ et $V([p_1, \dots, p_n], [k_1, \dots, k_n], K) = V([p_1, \dots, p_{n-1}], [k_1, \dots, k_{n-1}], K-k_n) + p_n$
• soit la solution optimale ne contient pas le produit $x_n$ et $V([p_1, \dots, p_n], [k_1, \dots, k_n], K) = V([p_1, \dots, p_{n-1}], [k_1, \dots, k_{n-1}], K)$

La remarque ci-dessus permet de définir, tout comme pour l'alignement de séquences, le terme général $M[i][j]$ d'une matrice à $n$ lignes et $K+1$ colonnes représentant $V([p_1, \dots, p_i], [k_1, \dots, k_i], j)$ :

Avec comme condition d'initialisation la première ligne :

• $M[1][j] = 0$ si $j < k_1$
• $M[1][j] = p_1$ si $j \geq k_1$

Une fois la matrice complete, de la même manière que pour l'alignement de séquences, on remonte la matrice pour trouver le sac à dos.

La complexité de cet algorithme est $\mathcal{O}(n\cdot K)$.

La mise en garde précédente est fondamentale, les deux algorithmes analyses tous les 2 toutes les possibilités pour une partie des données :

• l'algorithme de recherche exhaustive examine tous les contenus de sac à dos possible pour un contenant de $K$ et il y en a $2^n$
• l'algorithme de programmation dynamique examine tous les contenant de sacs à dos possible pour un contenu de $n$ objets et il y en a $K$

Enfin, si l'on s'intéresse uniquement à la complexité, comme il faut $\log_2(K)$ bits pour stocker $K$ les 2 algorithmes sont exponentiels !

Heuristique génétique

TBD voir :

• https://www.youtube.com/watch?v=MacVqujSXWE
• https://leria-info.univ-angers.fr/~jeanmichel.richer/uco_opt_combi_sac_a_dos.php (6.2)

Pour ne pas conclure

Le problème du sac à dos est un joli problème pouvant se résoudre de multiples manières, tant approchées avec une performance garantie qu'exact si les données le permettent (que l'exponentiel théorique n'est pas atteint). Il permet aussi de toucher du doigt un problème de complexité fin : les algorithmes dont on mesure la complexité avec des valeurs sont exponentiels par rapport à la taille de stockage de la valeur.

De plus, le problème du sac à dos est un problème très courant en pratique puisqu'il est à la base de nombreux problèmes en recherche opérationnelle comme :

• les problèmes de découpe (on maximise le nombre de pièces de dimensions fixés que l'on peut produire à partir d'un tissu)
• les problèmes d'équilibrage de charge
• ...

Et il se généralise à plusieurs dimensions.

Enfin, en l'écrivant sous la forme d'équations linéaires à résoudre comme on l'a fait pour la recherche exhaustive, il permet de s'initier à l'optimisation linéaire d'une part (qui admet des algorithmes polynomiaux de résolution) et à la programmation linéaire en nombre entier d'autre part (dont on ne connaît pas d'algorithme polynomial de résolution) en autorisant plusieurs exemplaires de chaque produits.