[PYTHON] Lösen von Rucksackproblemen mit den OP-Tools von Google - Üben der Grundlagen von Kombinationsoptimierungsproblemen

: bow_and_arrow: Zweck dieses Artikels

An einem einfachen Beispiel lernen Sie die Formulierung und Lösung des Rucksackproblems, das eines der typischen Probleme des Kombinationsoptimierungsproblems ist. Verwenden Sie nach der Formulierung die von Google in Python-Sprache erstellten OR-Tools als Tool, um die Lösung tatsächlich zu finden, und programmieren Sie sie, um die Lösung zu finden.

: bow_and_arrow: Über das Problem der Kombinationsoptimierung und seine Formulierung

Wenn Sie sich für etwas entscheiden, wird das Problem, das Muster der Kombination zu berücksichtigen, z. B. "Auswählen" oder "Nicht auswählen", die Elemente der Bedingung aus der Menge von Objekten zu extrahieren oder sie zu ordnen, als Kombinationsoptimierungsproblem bezeichnet. Ich werde.

Nun sei i oder j eine ganze Zahl ab 1, wie unten gezeigt, für die Konstanten a, b, c, die dem Problem und der Variablen x, für die die Lösung erhalten werden soll, im Voraus bekannt sind.

a_i　(i = 1,2,3,...,m)… Bekannte Konstanten\\
b_i　(i = 1,2,3,...,m)… Bekannte Konstanten\\
x_j　(j = 1,2,3,...,n)… X ist eine ganze Zahl

Das Problem, unter Verwendung der obigen Konstanten und Variablen eine Lösung in linearer Form (Additions- oder Multiplikationspolypolyse) zu finden, wird als ganzzahliges Programmierproblem bezeichnet und im Allgemeinen wie folgt formuliert.

<Formulierungsbeispiel>\hspace{250pt}\\
Zielfunktion: c_1x_1 + c_2x_2 + ... + c_nx_n\\
Bedingung: a_{i1}x_1 + a_{i2}x_2 + ... + a_{in}x_n ≦ b_i \\Wie auch immer, ich= 1,2,...,m\\
x_j ist eine ganze Zahl, j=1,2,...,n

Die Zielfunktion ist der Wert, bei dem die optimale Lösung durch Maximieren oder Minimieren des Werts gefunden wird, und der Löser berechnet ihn automatisch. Ein Solver ist ein Werkzeug zur Berechnung der optimalen Lösung für ein Optimierungsproblem, und wie eingangs erwähnt, werden hier OR-Tools verwendet. Verwenden Sie Python zum Programmieren.

: bow_and_arrow: Beispiel für ein Rucksackproblem

Das Rucksackproblem ist eines der typischen (oder Standard-) Probleme beim Kombinationsoptimierungsproblem. Ein typisches Problem ist ein repräsentatives Problem, das verschiedene gesellschaftliche Probleme wie Produktion / Vertrieb, Verkaufsplanung, Arbeitszeitplan und Informationsverarbeitung abstrahiert und in verschiedene Muster klassifiziert.

Hier wird das folgende Rucksackproblem als Beispiel aus dem Referenztext (in der Quelle aufgeführt) angeführt und die tatsächliche Lösung gesucht.

: language_balloon: Problem

Wie in der folgenden Artikeltabelle gezeigt, gibt es 5 Artikel, und jeder Artikel A bis E hat seinen eigenen.\\
Band a_j und Wert c_Ich weiß j.(j ist eine Indexnummer von 0 bis 4)\\
Auch die Kapazität des Rucksacks beträgt 12.\\
Ich möchte aus diesen Artikeln die Kombination der im Rucksack zu verpackenden Gegenstände bestimmen.\\
Das Gesamtvolumen der ausgewählten Artikel darf jedoch die Kapazität des Rucksacks nicht überschreiten.\\
Entscheiden Sie sich für eine Kombination von Elementen, die die Summe der Werte maximiert.\\

** Artikelliste **

Artikel	A	B	C	D	E
Indexnummer j	0	1	2	3	4
Band aj	3	4	6	1	5
Wert ci	6	7	8	1	4

: a: ** Antwort **

Betrachten Sie das Programm. Der Inhalt des Programms folgt im Wesentlichen dem OR-Tools-Handbuch von Google. (https://developers.google.com/optimization)

Schreiben Sie zu Beginn des Programms einen Zauber.

`knapsack.py`


from __future__ import print_function
from ortools.linear_solver import pywraplp

Da es durch den Mixed Integer Planning Solver gelöst wird, wird es unten deklariert.

`knapsack.py`


# Create the mip solver with the CBC backend.
solver = pywraplp.Solver('simple_mip_program',
    pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

Als nächstes definieren wir Konstanten.

`knapsack.py`


#Konstante Definition=================================================================

#Artikelvolumen
a = [3,4,6,1,5]
#Wert
c = [6,7,8,1,4]
#Rucksackkapazität
b = 12

Definieren Sie das Volumen, den Wert und die Rucksackkapazität des Artikels gemäß der obigen Problemstellung. Da es 5 Elemente gibt, werden die Werte in einem Array gespeichert. Die Artikelnummern sollten gemäß dem Index des Arrays von 0 an gezählt werden.

Definieren Sie die Variable x.

`knapsack.py`


#Variablendefinition=================================================================

# 1:Wählen/ 0:Nicht ausgewählt
x = {}
for j in range(5):
    x[j] = solver.BoolVar("x%i" % j)

Deklarieren Sie die Variable x, die bestimmt, welches Element oben ausgewählt werden soll. x nimmt den Wert 0 oder 1 an, 1, wenn Sie einen Artikel auswählen, 0, wenn Sie dies nicht tun. Der Löser berechnet und entscheidet, welchen Wert er annehmen soll.

Es ist endlich Zeit zu formulieren. In der Formulierung setzen wir den bedingten Ausdruck. In dieser Angelegenheit, ① Das Gesamtvolumen der ausgewählten Artikel darf die Kapazität des Rucksacks nicht überschreiten ② Legen Sie die Kombination von Elementen fest, die die Summe der Werte maximiert Ist eine Bedingung. Diese Bedingung wird als Einschränkungsbedingung bezeichnet, und was durch einen Ausdruck ausgedrückt wird, wird als Einschränkungsausdruck bezeichnet.

Der Einschränkungsausdruck ist unten definiert.

`knapsack.py`


#Einschränkungsausdruck===================================================================

#Die Summe der Volumina der ausgewählten Artikel darf die Kapazität des Rucksacks nicht überschreiten
solver.Add(solver.Sum([a[j] * x[j] for j in range(len(a))]) <= 12)

#Zielfunktion(Maximieren)
#Bestimmen Sie die Kombination von Elementen, die die Summe der Werte maximiert
solver.Maximize(solver.Sum([c[j] * x[j] for j in range(len(a))]))

Wie im zu Beginn gezeigt, werden die Bedingungen und Zielfunktionen definiert. Schreiben Sie abschließend eine Anweisung zur Berechnung der Lösung.

`knapsack.py`


#Lösungsausführung
status = solver.Solve()

Die Optimierungsberechnung wird oben durchgeführt und der Löser berechnet die optimale Lösung. Als Ergebnis der Berechnung wird xj in j von 0 bis 4 bestimmt, und es ist klar, welches Element auszuwählen ist. Überprüfen Sie das Berechnungsergebnis unten.

`knapsack.py`


if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
    print('Solution:')
    print('ok')
    print('Objective value =', solver.Objective().Value())
    print("culculate Time = ", solver.WallTime(), " milliseconds")

    #Element zur Auswahl
    print('select item')
    for j in range(len(a)):
        print(j,x[j].solution_value())
    
    #Wert
    print('total value')
    print(sum(c[j] * x[j].solution_value() for j in range(len(a))))

else:
    print('The problem does not have an optimal solution.')

Dies ist das Ende der Programmierung. Das tatsächliche Ausführungsergebnis ist wie folgt.

Solution: ok Objective value = 17.0 culculate Time = 158 milliseconds select item 0 1.0 1 1.0 2 0.0 3 0.0 4 1.0 total value 17.0

Als Ergebnis der Optimierungsberechnung wählt der Artikel 0,1,4 (A, B, E) aus und sein Wert ist

\begin{eqnarray}

Wert&=&c_0+c_1+c_4\\
&=&6+7+4\\
&=&17

\end{eqnarray}

Es stellte sich heraus. Das ist alles für die Optimierungsberechnung.

Unten ist die gesamte Quelle.

`knapsack.py`


from __future__ import print_function
from ortools.linear_solver import pywraplp

# Create the mip solver with the CBC backend.
solver = pywraplp.Solver('simple_mip_program',
    pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)


#Konstante Definition=================================================================

#Artikelvolumen
a = [3,4,6,1,5]
#Wert
c = [6,7,8,1,4]
#Rucksackkapazität
b = 12

#Variablendefinition=================================================================

# 1:Wählen/ 0:Nicht ausgewählt
x = {}
for j in range(5):
    x[j] = solver.BoolVar("x%i" % j)

#Einschränkungsausdruck===================================================================

#Die Summe der Volumina der ausgewählten Artikel darf die Kapazität des Rucksacks nicht überschreiten
solver.Add(solver.Sum([a[j] * x[j] for j in range(len(a))]) <= 12)

#Zielfunktion(Maximieren)
#Bestimmen Sie die Kombination von Elementen, die die Summe der Werte maximiert
solver.Maximize(solver.Sum([c[j] * x[j] for j in range(len(a))]))

#Lösungsausführung
status = solver.Solve()

if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
    print('Solution:')
    print('ok')
    print('Objective value =', solver.Objective().Value())
    print("culculate Time = ", solver.WallTime(), " milliseconds")

    #Element zur Auswahl
    print('select item')
    for j in range(len(a)):
        print(j,x[j].solution_value())
    
    #Wert
    print('total value')
    print(sum(c[j] * x[j].solution_value() for j in range(len(a))))

else:
    print('The problem does not have an optimal solution.')

: bow_and_arrow: Ausstellung

Dieser Artikel basiert auf den in den folgenden Referenztexten beschriebenen Übungen zur mathematischen Optimierung.

■ Referenztext "Mathematische Optimierung von IT-Texten" Takato Kuno et al. [Autor] Informationsverarbeitungsgesellschaft [Bearbeiten]

: bow_and_arrow: Zugehörige Informationen

Andere verwandte Artikel

: triangular_flag_on_post: Lösen mathematischer Optimierungsmodellübungen mit den OR-Tools von Google (1) Das einfachste Problem beim Füllen von Massen https://qiita.com/ttlabo/items/7e8c93f387814f99931f

: triangular_flag_on_post: [Teil 1] Was ist Optimierung? - Lernmaterialien zum Erlernen der mathematischen Optimierung https://qiita.com/ttlabo/items/e6970c6e85cce9ff4e34

: bow_and_arrow: Meinungen etc.

Wenn Sie Meinungen oder Korrekturen haben, lassen Sie es uns bitte wissen.