Résoudre les problèmes de sac à dos à l'aide de pyomo et glpk

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.

Installation

# 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.

Code par pyomo

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)

Description du code

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.

Exécution du code et résultats d'exécution

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
        }
    ]
}

Interprétation des résultats

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."

Bons points de pyomo

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

Résoudre les problèmes de sac à dos à l'aide de pyomo et glpk
Résolvez le problème du sac à dos Python avec la méthode de branche et liée
Animer les bases de la planification dynamique et des problèmes de sac à dos
Résolvez le problème de Monty Hall
Résolvez le problème japonais lors de l'utilisation du module CSV en Python.
Illustration des résultats du problème du sac à dos
Essayez de résoudre le problème de minimisation des fonctions en utilisant l'optimisation des groupes de particules
Comment résoudre le problème d'emballage du bac
Résolvez le problème du voyageur de commerce avec OR-Tools
Résolvez le problème maximum de sous-tableau en Python
Résolvez le problème du voyageur de commerce asymétrique Python avec la méthode de branche et de liaison
Visualisez les données d'itinéraires ferroviaires et résolvez les problèmes d'itinéraires les plus courts (Python + Pandas + NetworkX)
Essayez de résoudre le problème du fizzbuzz avec Keras
Vérification des méthodes et des variables à l'aide de la bibliothèque voir
Répondre à l'image redimensionnée à l'aide de Flask et PILImage
[Chez Coder] Résoudre le problème de la dichotomie
Résolvez le problème du sac à dos Python avec l'algorithme glouton
Mémorandum de problème de sac à dos
Essayez de résoudre le problème d'affectation du médecin de formation avec Python
Créez un graphique à l'aide du bouton et du curseur de l'intrigue
Envoyez et recevez Gmail via l'API Gmail en utilisant Python
J'ai essayé de résoudre le problème avec Python Vol.1