knapsack

Tornister

Das Rucksackproblem ist ein bekanntes Optimierungsproblem. Es kommt beispielsweise beim Verpacken von Schiffscontainern vor. Ein Versandbehälter hat eine Gewichtskapazität, die er aufnehmen kann. Bei einer Sammlung von zu versendenden Artikeln, bei denen jeder Artikel einen Wert und ein Gewicht hat, besteht das Problem darin, die optimalen Artikel auszuwählen, die in den Versandbehälter gepackt werden sollen. Dieses Optimierungsproblem kann als Ziel mit einer Einschränkung definiert werden:

• Ziel: Frachtwert maximieren (Summe der Werte der ausgewählten Artikel).
• Einschränkung: Das Gesamtfrachtgewicht (Summe der Gewichte der ausgewählten Artikel) muss kleiner oder gleich der Kapazität des Containers sein.

Dieses Beispiel löst ein solches Rucksackproblem, indem es als eingeschränktes quadratisches Modell (CQM) umformuliert und an einen Leap-Hybrid-CQM-Löser übermittelt wird.

Verwendung

Um die Standarddemo auszuführen, geben Sie den folgenden Befehl ein:

python knapsack.py

Geben Sie den folgenden Befehl ein, um die verfügbaren Optionen anzuzeigen:

python knapsack.py --help

Mit Befehlszeilenargumenten können Sie einen von mehreren Datensätzen (im Ordner /data ) auswählen und die Frachtkapazität festlegen. Die Datendateien sind als Zeilen mit Elementen formuliert, die jeweils als Gewichtungs- und Wertpaar definiert sind.

Codeübersicht

Der Code in knapsack.py umfasst drei Hauptfunktionen:

• build_knapsack_cqm() erstellt ein CQM, indem ein Ziel und eine Einschränkung wie folgt festgelegt werden:

  • Ziel: Für jedes Element werden binäre Variablen erstellt und ihnen wird eine lineare Tendenz zugewiesen, die dem negativen Wert des Elementwerts entspricht. Die Minimierung dieses Ziels durch die Auswahl eines optimalen Artikelsatzes ist gleichbedeutend mit der Maximierung des Gesamtwerts der Fracht. Lösungen legen einen Wert von 1 für ausgewählte Elemente und 0 für nicht ausgewählte Elemente fest.
  • Einschränkung: Es wird ein quadratisches Modell mit den zuvor erstellten binären Variablen erstellt, bei dem die linearen Bias dem Gewicht jedes Artikels entsprechen, mit der Anforderung, dass das Gesamtgewicht die Kapazität des Behälters nicht überschreiten darf.

• parse_inputs() ist eine Hilfsfunktion, die Daten aus den Beispieldateien liest.

• parse_solution() analysiert die vom Solver zurückgegebenen Ergebnisse und zeigt sie an.

Lizenz

Veröffentlicht unter der Apache-Lizenz 2.0. Siehe LICENSE-Datei.