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]

001.JPG

: bow_and_arrow: Related information

Other related articles

: triangular_flag_on_post: Solving mathematical optimization model exercises with Google's OR-Tools (1) The easiest mass filling problem https://qiita.com/ttlabo/items/7e8c93f387814f99931f

: triangular_flag_on_post: [Part 1] What is optimization? --Study materials for learning mathematical optimization https://qiita.com/ttlabo/items/e6970c6e85cce9ff4e34

: bow_and_arrow: Opinions etc.

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

Recommended Posts

Solving Knapsack Problems with Google's OR-Tools-Practicing the Basics of Combinatorial Optimization Problems
Solving 4-color problems with combinatorial optimization
Solving nurse scheduling problems with combinatorial optimization
Solving school district organization problems with combinatorial optimization
Solving the N Queen problem with combinatorial optimization
Solving the N Queens problem with combinatorial optimization
○○ Solving problems in the Department of Mathematics by optimization
Solving Mathematical Optimization Model Exercises with Google's OR-Tools (3) Production Optimization Problems
Pave the road with combinatorial optimization
The power of combinatorial optimization solvers
Solving game theory with combinatorial optimization
Solve combinatorial optimization problems with Google's OR-Tools (5) Decide on a date course
Combinatorial optimization to find the hand of "Millijan"
Minimize the number of polishings by combinatorial optimization
Judging the finish of mahjong by combinatorial optimization
Solving the Python knapsack problem with the greedy algorithm
Solving knapsack problems with genetic algorithms and MGG models
Animate the basics of dynamic programming and the knapsack problem
Let's decide the lecture of PyCon JP 2016 by combinatorial optimization
Let's decide the position of the fire station by combinatorial optimization
Grouping games with combinatorial optimization
Combinatorial optimization with quantum annealing
Solving the nurse scheduling problem (shift optimization) with a genetic algorithm
Solving the Maze with Python-Supplement to Chapter 6 of the Algorithm Quick Reference-
Solving "cubes in cubes" by combinatorial optimization
Maximize restaurant sales with combinatorial optimization
Go see whales with combinatorial optimization
Getting Started with Python Basics of Python
Review of the basics of Python (FizzBuzz)
Design of experiments and combinatorial optimization
Basics of touching MongoDB with MongoEngine
Illustration of the results of the knapsack problem
Solving the amplitude of interferometer observations
About the basics list of Python basics
Solving the phase of interferometer observations
Learn the basics of Python ① Beginners
[AtCoder explanation] Control the A, B, C problems of ABC182 with Python!
[AtCoder explanation] Control the A, B, C problems of ABC186 with Python!
[AtCoder explanation] Control the A, B, C problems of ABC185 with Python!
[AtCoder explanation] Control the A, B, C problems of ABC187 with Python!
[AtCoder explanation] Control the A, B, C problems of ABC184 with Python!
Basics of orbit generation (solving nonlinear optimal control problems using Scipy's optimize)