Mit pyomo, einer Optimierungsmodellierungssprache, können Sie einige Optimierungsprobleme lösen, indem Sie einfach Variablen, Einschränkungen und Zielfunktionen angeben. Hier werden wir als Beispiel das Rucksackproblem lösen.
# pip install Pyomo
# pacman -S glpk
glpk ist ein Löser zur Lösung von Optimierungsproblemen. Lösen Sie das in pyomo geschriebene Problem mit glpk.
mkp_concrete.py
from pyomo.environ import *
v = {'applepie':8, 'beer':3, 'chocolatecake':6, 'duckmeat':11}
w = {'applepie':5, 'beer':7, 'chocolatecake':4, 'duckmeat':3}
limit = 14
M = ConcreteModel()
M.I = Set(initialize=v.keys())
M.x = Var(M.I, within=Binary)
M.value = Objective(expr=sum(v[i]*M.x[i] for i in M.I), sense=maximize)
M.weight = Constraint(expr=sum(w[i]*M.x[i] for i in M.I) <= limit)
Mit pyomo können Sie zwischen einem konkreten Modell und einem abstrakten Modell wählen. Konkretes Modell bedeutet ein konkretes Modell.
Set bedeutet eine Menge von Elementen und Var bedeutet eine Variable. Der Variablentyp wird durch innerhalb von = Binär angegeben. Hier definiert die Variable 0-1, ob es sich um ein Element handelt, das in die Tasche gelegt werden soll.
Ziel ist eine objektive Funktion. Die Zielfunktion des Rucksackproblems besteht darin, den Gesamtwert der Gegenstände in der Tasche zu maximieren. Die Maximierung wird durch sense = maxim angegeben.
Einschränkung ist eine Einschränkungsbedingung. Die Einschränkung des Rucksackproblems bedeutet, dass das Gesamtgewicht kleiner oder gleich dem angegebenen Wert ist.
Lauf.
$ pyomo solve --solver=glpk mkp_concrete.py
[ 0.00] Setting up Pyomo environment
[ 0.00] Applying Pyomo preprocessing actions
[ 0.01] Creating model
[ 0.01] Applying solver
[ 0.03] Processing results
Number of solutions: 1
Solution Information
Gap: 0.0
Status: optimal
Function Value: 25.0
Solver results file: results.json
[ 0.03] Applying Pyomo postprocessing actions
[ 0.03] Pyomo Finished
Das Ausführungsergebnis wird in der folgenden Datei gespeichert.
results.json
{
"Problem": [
{
"Lower bound": 25.0,
"Name": "unknown",
"Number of constraints": 2,
"Number of nonzeros": 5,
"Number of objectives": 1,
"Number of variables": 5,
"Sense": "maximize",
"Upper bound": 25.0
}
],
"Solution": [
{
"number of solutions": 1,
"number of solutions displayed": 1
},
{
"Constraint": "No values",
"Gap": 0.0,
"Message": null,
"Objective": {
"value": {
"Value": 25.0
}
},
"Problem": {},
"Status": "optimal",
"Variable": {
"x[applepie]": {
"Value": 1.0
},
"x[chocolatecake]": {
"Value": 1.0
},
"x[duckmeat]": {
"Value": 1.0
}
}
}
],
"Solver": [
{
"Error rc": 0,
"Statistics": {
"Branch and bound": {
"Number of bounded subproblems": "1",
"Number of created subproblems": "1"
}
},
"Status": "ok",
"Termination condition": "optimal",
"Time": 0.007568359375
}
]
}
Das obige Ergebnis kann wie folgt interpretiert werden.
"Legen Sie Apfelkuchen, Schokoladenkuchen und Entenfleisch für einen Maximalwert von 25,0 in Ihre Tasche."
Der Gurobi-Optimierer ist besser, aber Pyomo kann kostenlos verwendet werden.
Die Optimierungsmodellierungssprache beschreibt ein Modell, mit dem der Löser das Problem lösen kann. Mit anderen Worten, Sie müssen nicht über den Teil des Algorithmus nachdenken, den der Solver ausführt.
Mit anderen Worten, mit Pyomo und Gurobi Optimizer müssen Sie sich nur auf die Modellierung des Problems konzentrieren.
In Bezug auf die Geschwindigkeit kann es schneller sein, einen Algorithmus auszuwählen, aber es gibt einige Geschwindigkeiten, die der Solver ausführen kann.