knapsack

Sac à dos

Le problème du sac à dos est un problème d’optimisation bien connu. On le rencontre par exemple dans l'emballage des conteneurs maritimes. Un conteneur maritime a une capacité de poids qu’il peut supporter. Étant donné un ensemble d’articles à expédier, où chaque article a une valeur et un poids, le problème est de sélectionner les articles optimaux à emballer dans le conteneur d’expédition. Ce problème d'optimisation peut être défini comme un objectif avec une contrainte :

• Objectif : Maximiser la valeur du fret (somme des valeurs des articles sélectionnés).
• Contrainte : Le poids total du fret (somme des poids des articles sélectionnés) doit être inférieur ou égal à la capacité du conteneur.

Cet exemple résout un tel problème de sac à dos en le reformulant sous la forme d'un modèle quadratique contraint (CQM) et en le soumettant à un solveur CQM hybride Leap.

Usage

Pour exécuter la démo par défaut, entrez la commande :

python knapsack.py

Pour afficher les options disponibles, entrez la commande :

python knapsack.py --help

Les arguments de ligne de commande vous permettent de sélectionner l'un des nombreux ensembles de données (sous le dossier /data ) et de définir la capacité de transport. Les fichiers de données sont formulés sous forme de lignes d'éléments, chacun défini comme une paire de poids et de valeur.

Présentation du code

Le code de knapsack.py comprend trois fonctions principales :

• build_knapsack_cqm() crée un CQM en définissant un objectif et une contrainte comme suit :

  • Objectif : Des variables binaires sont créées pour chaque élément et se voient attribuer un biais linéaire égal à la valeur négative de la valeur de l'élément. Minimiser cet objectif, en sélectionnant un ensemble optimal d’articles, équivaut à maximiser la valeur totale du fret. Les solutions définissent une valeur de 1 pour les éléments sélectionnés et de 0 pour les éléments non sélectionnés.
  • Contrainte : Un modèle quadratique avec les variables binaires créées précédemment, où les biais linéaires sont définis égaux au poids de chaque article, est créé avec l'exigence que le poids total ne doit pas dépasser la capacité du conteneur.

• parse_inputs() est une fonction utilitaire qui lit les données des fichiers d'exemple.

• parse_solution() analyse et affiche les résultats renvoyés par le solveur.

Licence

Publié sous la licence Apache 2.0. Voir fichier LICENCE.