[PYTHON] Optimization learned with OR-Tools Part0 [Introduction]

This blog is what

We will learn mathematical optimization using OR-Tools developed by Google. Most of the content is based on this book. Practical Python AI Projects: Mathematical Models of Optimization Problems with Google OR-Tools (English Edition)

Click here for a list of codes by author The code described in this blog is almost the same as the original one of the author, and it is only partially corrected to Japanese.

Mathematical rigor and theoretical commentary are of low priority. Please forgive me.

This time: Introduced

Based on a simple example ・ What is the optimization problem? ・ How do you use OR-Tools? I will study

Scene setting

You are in charge of amphibians at a pet store. It seems that they keep ** toads, salamanders, and newts in the same aquarium **. I want to keep as many as possible, but the food is limited. By the way, ** food is earthworms, crickets, flies ** (why is this an example?) Depending on the type, how many foods you eat in a day is different, ** How can you keep the most in total? **

Amount of food to eat per day for each amphibian

Formulation

First, set the coefficient of determination. This time, we will ask for "the number of toads, salamanders, and newts that maximizes the total".

\begin{align}
&x_0 :Toad\\
&x_1 :Salamander\\
&x_2 :Newt\\
\end{align}\\
However, 0\leq x_i \leq 1000

The function I want to maximize this time is

x_0 + x_1 + x_2

roof. It's OK if you keep 1000 animals each! However, there are restrictions on food. We have 1500 earthworms, we eat 2 toads a day, 1 salamander, and 1 newt.

2x_0 + x_1 + x_2 \leq 1500

Similarly for crickets and flies.

x_0 + 3x_1 + 2x_2 \leq 3000\\
x_0 + 2x_1 + 3x_2 \leq 5000

Now, implementation

It takes the form of defining a solver (s) and adding variables, objective functions, and constraints (Add). When defining, the solver title (this time "coexistence of amphibians") and the solver to be used (this time GLOP) are specified as arguments. GLOP is a linear programming solver.

coexistence.py

from ortools.linear_solver import pywraplp

def solve_coexistence():
    t = 'Amphibian coexistence'
    s = pywraplp.Solver(t, pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)
    
    x = [s.NumVar(0, 1000, 'x[%i]' % i) for i in range(3)]  #　0 <= x <=1000. Determinant variable
    pop = s.NumVar(0, 3000, 'pop')                          # 0 <= pop <=3000. Objective variable
    
    s.Add(2*x[0] + x[1] + x[2] <= 1500)       #Earthworm constraint
    s.Add(x[0] + 3*x[1] + 2*x[2] <= 3000)     #Cricket constraint
    s.Add(x[0] + 2*x[1] + 3*x[2] <= 4000)     #Fly constraint
    s.Add(pop == x[0] + x[1] + x[2])          #Objective function
    s.Maximize(pop)                           #Specify that you want to maximize pop
    s.Solve()                                 #solve


    ##Returns the value of the objective function and the value of the decision variable
    return pop.SolutionValue(), [e.SolutionValue() for e in x]

Click here for the code to execute

test_coexistence.py

from __future__ import print_function
from coexistence import solve_coexistence

pop, x = solve_coexistence()  #Call the defined function and store the result
T = [['type', 'number']]          #Column name when displaying results
for i in range(3):
    T.append([['Toad','Salamander','Newt'][i], x[i]])   #Add name and population to i-line
T.append(['total', pop])

for e in T:
    print(e[0], e[1])

Execution result

Yes this is the optimal solution. There are too many newts and you can laugh I don't know that newts eat a lot of earthworms and crickets (few) and eat a lot of flies, so I got a lot of them. In reality, salamanders sell best, so I want to put in a lot of them, and newts don't sell well, so I don't want to do that, but this time around, it's an introduction.

I just realized that the next time I will talk more about how to use OR-Tools. Then what did you do this time?