Si vous utilisez pyomo, qui est un langage de modélisation d'optimisation, vous pouvez résoudre certains problèmes d'optimisation simplement en spécifiant des variables, des contraintes et des fonctions objectives. Ici, nous allons résoudre le problème du sac à dos à titre d'exemple.
# pip install Pyomo
# pacman -S glpk
glpk est un solveur pour résoudre des problèmes d'optimisation. Résolvez le problème écrit en pyomo avec 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)
Avec pyomo, vous pouvez choisir entre un modèle concret et un modèle abstrait. Modèle concret signifie un modèle concret.
Set signifie un ensemble d'éléments et Var signifie une variable. Le type de variable est spécifié par within = Binary, mais ici la variable 0-1 définit s'il s'agit ou non d'un article à mettre dans le sac.
L'objectif est une fonction objective. La fonction objective du problème du sac à dos est de maximiser la valeur totale des articles dans le sac. La maximisation est spécifiée par sense = maximiser.
La contrainte est une condition de contrainte. La contrainte sur le problème du sac à dos signifie que le poids total est inférieur ou égal à la valeur spécifiée.
Courir.
$ 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
Le résultat de l'exécution est stocké dans le fichier suivant.
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
}
]
}
Le résultat ci-dessus peut être interprété comme suit.
"Mettez les pommes, le gâteau au chocolat, la viande de canard dans votre sac pour une valeur maximale de 25,0."
L'optimiseur gurobi est de meilleure qualité, mais pyomo est gratuit.
Le langage de modélisation d'optimisation décrit un modèle permettant au solveur de résoudre le problème. En d'autres termes, vous n'avez pas à penser à la partie de l'algorithme que fait le solveur.
En d'autres termes, avec l'optimiseur pyomo et gurobi, vous n'avez qu'à vous concentrer sur la modélisation du problème.
En termes de vitesse, il peut être plus rapide de choisir un algorithme, mais il y a une certaine vitesse pour laisser le solveur le faire.
Recommended Posts