Solve the knapsack problem using pyomo and glpk

If you use pyomo, which is an optimization modeling language, you can solve some optimization problems just by specifying variables, constraints, and objective functions. Here, we will solve the knapsack problem as an example.

Installation

# pip install Pyomo
# pacman -S glpk

glpk is a solver for solving optimization problems. Solve the problem written in pyomo with glpk.

Code by 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)

Code description

With pyomo, you can choose between a concrete model and an abstract model. Concrete Model means a concrete model.

Set means a set of items and Var means a variable. The variable type is specified by within = Binary, but here the 0-1 variable defines whether or not it is an item to be put in the bag.

Objective is an objective function. The objective function of the knapsack problem is to maximize the total value of the items in the bag. Maximization is specified by sense = maximize.

Constraint is a constraint. The constraint on the knapsack problem means that the total weight is less than or equal to the specified value.

Code execution and execution results

Run.


$ 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

The execution result is stored in the following file.

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

Interpretation of results

The above result can be interpreted as follows.

"Put applepie, chocolatecake, duckmeat in your bag for maximum value of 25.0."

Good points of pyomo

The gurobi optimizer is better quality, but pyomo is free to use.

An optimized modeling language describes a model to help the solver solve a problem. In other words, you don't have to think about the algorithm of the part that the solver does.

In other words, with pyomo and gurobi optimizer, you only have to focus on modeling the problem.

In terms of speed, it may be faster to choose an algorithm, but there are some speeds to let the solver do.

Recommended Posts

Solve the knapsack problem using pyomo and glpk
Solve the Python knapsack problem with a branch and bound method
Animate the basics of dynamic programming and the knapsack problem
Solve the Monty Hall problem
Solve the Japanese problem when using the CSV module in Python.
Illustration of the results of the knapsack problem
Try to solve the function minimization problem using particle swarm optimization
How to solve the bin packing problem
Solve the traveling salesman problem with OR-Tools
Solve the maximum subarray problem in Python
Solve the Python asymmetric traveling salesman problem with a branch and bound method
Visualize railway line data and solve the shortest path problem (Python + Pandas + NetworkX)
Try to solve the fizzbuzz problem with Keras
Checking methods and variables using the library see
Response the resized image using Flask and PILImage
[At Coder] Solve the problem of binary search
Solving the Python knapsack problem with the greedy algorithm
Knapsack problem memorandum
Try to solve the internship assignment problem with Python
Creating a graph using the plotly button and slider
Send and receive Gmail via the Gmail API using Python
I tried to solve the problem with Python Vol.1