[PYTHON] Die Leistungsfähigkeit von Kombinationsoptimierungslösern

Was ist das

Probieren wir die Leistung des Lösers aus, der das Optimierungsproblem mithilfe eines zufälligen und einfachen Problems (Rucksackproblem) löst.

Erstellen Sie ein zufälliges Rucksackproblem

Erstellen Sie ein Rucksackproblem [^ 1] mit n Elementen. Die optimale Lösung wird auf etwa 80% der Gesamtzahl der Artikel eingestellt.

python

import numpy as np
from pulp import *
def make(n):
    np.random.seed(1)
    w = 1 + np.random.rand(n)
    p = w + np.random.randn(n)*0.1
    m = LpProblem(sense=LpMaximize)
    v = [LpVariable('x%d'%i, cat=LpBinary) for i in range(n)]
    m += lpDot(p, v)
    m += lpDot(w, v) <= int(n*1.25)
    return v, m

Überprüfen Sie die Berechnungszeit

Sehen wir uns die Berechnungszeit an, während Sie die Anzahl der Elemente ändern. Der Optimierungslöser verwendet GUROBI 6.51.

python

v, m = make(10000)
%timeit -n 3 m.solve(GUROBI_CMD())
sum(value(x) for x in v)
>>>
3 loops, best of 3: 222 ms per loop
8254.0

python

v, m = make(20000)
%timeit -n 3 m.solve(GUROBI_CMD())
sum(value(x) for x in v)
>>>
3 loops, best of 3: 486 ms per loop
16470.0

python

v, m = make(50000)
%timeit -n 3 m.solve(GUROBI_CMD())
sum(value(x) for x in v)
>>>
3 loops, best of 3: 1.38 s per loop
41237.0

python

v, m = make(100000)
%timeit -n 3 m.solve(GUROBI_CMD())
sum(value(x) for x in v)
>>>
3 loops, best of 3: 2.64 s per loop
82458.0

Zusammenfassung

Wenn es n Elemente gibt, gibt es $ 2 ^ n $ mögliche Auswahlmöglichkeiten. Da diese Berechnungszeit die Zeit ist, um die genaue Lösung zu finden, untersuchen wir (fast) alle diese Möglichkeiten [^ 2].

――Die Anzahl möglicher Lösungen steigt exponentiell mit der Anzahl der Elemente. Die Berechnungszeit ist jedoch nahezu linear. ――Es dauerte weniger als 3 Sekunden, um die enorme Kombination von 10 bis 30.000 Potenz herauszufinden [^ 3].

Sie können sehen, wie hoch die Leistung dieser aktuellen Löser ist. Es sollte jedoch beachtet werden, dass die Leistung in Abhängigkeit von der Art des Kombinationsoptimierungsproblems und der Formulierungsmethode erheblich verschlechtert sein kann.

Das Rucksackproblem ist NP-vollständig, aber Sie können die hohe Leistung des Lösers auch im Problem der maximalen Gewichtsanpassung mit Klasse P (Vergleich der Lösungen beim Problem der Gewichtsanpassung sehen. 7fd199a95d78a6f3b741)).

Referenz

• Kombinationsoptimierung verwenden
• Herr Miyashiros Memo of Integer Planning --Knapsack Problem im Zusammenhang
• Kombinationsoptimierung - Typisches Problem - Rucksackproblem
• Golferwartungen mithilfe dynamischer Optimierung ermitteln
• Darstellung der Ergebnisse des Rucksackproblems
• Löser im Zusammenhang
• Einführung in die Formulierung durch Integer-Programmierung
• Einführung in Integer Planning Solver
• Mathematische Optimierung durch ZIMPL-Sprache und SCIP
  • Gurobi Optimizer

das ist alles

[^ 1]: Das Rucksackproblem ist ein schwieriges NP-Problem, und es wird angenommen, dass es keine Lösung in der Größenordnung des Polymorphismus gibt, aber es kann durch einen Löser effizient gelöst werden. [^ 2]: Wir finden eine Lösung, bei der die Verhältnisdifferenz ε oder weniger in Bezug auf den Wert der Zielfunktion der exakt optimalen Lösung beträgt. Standardmäßig scheint es ε = 0,0001 zu sein (Referenz Hinweis zur Ganzzahlprogrammierung). [^ 3]: Sogar die Anzahl der Atome im Universum beträgt ungefähr $ 10 ^ {80} $, was viel kleiner ist.