[PYTHON] 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.