Solving Knapsack Problems with Google's OR-Tools-Practicing the Basics of Combinatorial Optimization Problems

: bow_and_arrow: Purpose of this article

You will learn the formulation and solution of the knapsack problem, which is one of the typical combinatorial optimization problems, through simple examples. In addition, after formulating, use Google's OR-Tools in Python language as a tool to actually find the solution, and actually program to find the solution.

: bow_and_arrow: Combinatorial optimization problem and its formulation

When deciding something, the problem of thinking about the pattern of the combination, such as selecting "select" or "not selecting" things, extracting the elements of the condition from the set of objects, or ordering them, is called a combinatorial optimization problem. I will.

Now, let i or j be an integer starting from 1 as shown below, for the constants a, b, c that are known in advance by the problem and the variable x for which the solution is to be obtained.

a_i　(i = 1,2,3,...,m)… Constants known in advance\\
b_i　(i = 1,2,3,...,m)… Constants known in advance\\
x_j　(j = 1,2,3,...,n)… X is an integer

The problem of finding a solution in the line form (addition or multiplication polynomial) using the above constants and variables is called an integer programming problem, and is generally formulated as follows.

<Formulation example>\hspace{250pt}\\
Objective function: c_1x_1 + c_2x_2 + ... + c_nx_n\\
Condition: a_{i1}x_1 + a_{i2}x_2 + ... + a_{in}x_n ≦ b_i \\However, i= 1,2,...,m\\
x_j is an integer, j=1,2,...,n

The objective function is the value at which the optimal solution is found by maximizing or minimizing that value, which the solver automatically calculates. A solver is a tool for calculating the optimum solution for an optimization problem, and as mentioned at the beginning, OR-Tools is used here. Use Python for programming.

: bow_and_arrow: Knapsack problem example

The knapsack problem is one of the typical (or standard) problems in combinatorial optimization problems. A typical problem is a representative problem that abstracts various problems existing in society such as production / logistics, sales planning, work schedule, and information processing, and classifies them into several patterns.

Here, the following knapsack problem is quoted as an example from the reference text (listed in the source), and the actual solution is sought.

: speech_balloon: Problem

As shown in the item table below, there are 5 items, and each item A to E has its own item.\\
Volume a_j and value c_I know j.(j is an index number from 0 to 4)\\
Also, the capacity of the knapsack is 12.\\
I want to decide the combination of items to be packed in the knapsack from these items.\\
However, the total volume of the selected items must not exceed the capacity of the knapsack.\\
Decide on a combination of items that maximizes the sum of values.\\

** Item list **

item	A	B	C	D	E
Index number j	0	1	2	3	4
Volume aj	3	4	6	1	5
Value ci	6	7	8	1	4

: a: ** Answer **

Consider the program. The contents of the program basically follow Google's OR-Tools guide. (https://developers.google.com/optimization)

Write a spell at the beginning of the program.

`knapsack.py`


from __future__ import print_function
from ortools.linear_solver import pywraplp

Since it is solved by the mixed integer programming solver, it is declared below.

`knapsack.py`


# Create the mip solver with the CBC backend.
solver = pywraplp.Solver('simple_mip_program',
    pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

Next, we define constants.

`knapsack.py`


#Constant definition=================================================================

#Item volume
a = [3,4,6,1,5]
#value
c = [6,7,8,1,4]
#Knapsack capacity
b = 12

Define the volume, value, and knapsack capacity of the item according to the problem statement above. Since there are 5 items, we will hold the values in an array. Item numbers should be counted from 0 according to the index of the array.

Define the variable x.

`knapsack.py`


#Variable definition=================================================================

# 1:Choose/ 0:Not selected
x = {}
for j in range(5):
    x[j] = solver.BoolVar("x%i" % j)

Declare the variable x that determines which item to choose above. x takes a value of 0 or 1, 1 if you choose an item, 0 if you don't. The solver calculates and decides which value to take.

It's finally time to formulate. In the formulation, we will set the conditional expression. In this problem, ① The total volume of the selected items must not exceed the capacity of the knapsack. ② Decide the combination of items that maximizes the sum of values Is a condition. This condition is called a constraint condition, and what is expressed by an expression is called a constraint expression.

The constraint expression is defined below.

`knapsack.py`


#Constraint expression===================================================================

#The sum of the volumes of the selected items must not exceed the capacity of the knapsack
solver.Add(solver.Sum([a[j] * x[j] for j in range(len(a))]) <= 12)

#Objective function(Maximize)
#Determine the combination of items that maximizes the sum of values
solver.Maximize(solver.Sum([c[j] * x[j] for j in range(len(a))]))

As shown in the at the beginning, the condition and objective function are defined. Finally, write an instruction to calculate the solution.

`knapsack.py`


#Solution execution
status = solver.Solve()

The optimization calculation is performed above, and the solver calculates the optimum solution. As a result of the calculation, xj is determined in j from 0 to 4, and it is clear which item to select. Check the calculation result below.

`knapsack.py`


if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
    print('Solution:')
    print('ok')
    print('Objective value =', solver.Objective().Value())
    print("culculate Time = ", solver.WallTime(), " milliseconds")

    #Item to select
    print('select item')
    for j in range(len(a)):
        print(j,x[j].solution_value())
    
    #value
    print('total value')
    print(sum(c[j] * x[j].solution_value() for j in range(len(a))))

else:
    print('The problem does not have an optimal solution.')

This is the end of programming. The actual execution result is as follows.

Solution: ok Objective value = 17.0 culculate Time = 158 milliseconds select item 0 1.0 1 1.0 2 0.0 3 0.0 4 1.0 total value 17.0

As a result of the optimization calculation, the item selects 0,1,4 (A, B, E), and its value is

\begin{eqnarray}

value&=&c_0+c_1+c_4\\
&=&6+7+4\\
&=&17

\end{eqnarray}

It turned out to be. That's all for the optimization calculation.

Below is the entire source.

`knapsack.py`


from __future__ import print_function
from ortools.linear_solver import pywraplp

# Create the mip solver with the CBC backend.
solver = pywraplp.Solver('simple_mip_program',
    pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)


#Constant definition=================================================================

#Item volume
a = [3,4,6,1,5]
#value
c = [6,7,8,1,4]
#Knapsack capacity
b = 12

#Variable definition=================================================================

# 1:Choose/ 0:Not selected
x = {}
for j in range(5):
    x[j] = solver.BoolVar("x%i" % j)

#Constraint expression===================================================================

#The sum of the volumes of the selected items must not exceed the capacity of the knapsack
solver.Add(solver.Sum([a[j] * x[j] for j in range(len(a))]) <= 12)

#Objective function(Maximize)
#Determine the combination of items that maximizes the sum of values
solver.Maximize(solver.Sum([c[j] * x[j] for j in range(len(a))]))

#Solution execution
status = solver.Solve()

if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
    print('Solution:')
    print('ok')
    print('Objective value =', solver.Objective().Value())
    print("culculate Time = ", solver.WallTime(), " milliseconds")

    #Item to select
    print('select item')
    for j in range(len(a)):
        print(j,x[j].solution_value())
    
    #value
    print('total value')
    print(sum(c[j] * x[j].solution_value() for j in range(len(a))))

else:
    print('The problem does not have an optimal solution.')

: bow_and_arrow: Exhibit

This article is based on the exercises described in the following reference texts on mathematical optimization.

■ Reference text "IT Text Mathematical Optimization" Shizuka Kuno, et al. [Author] Information Processing Society of Japan [edit]

: bow_and_arrow: Related information

: bow_and_arrow: Opinions etc.

If you have any opinions or corrections, please let us know.