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

bait Toad Salamander Newt Number that can be prepared
Earthworm 2 1 1 1500
Cricket 1 3 2 3000
Flies 1 2 3 5000

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

type number
Toad 100.0
Salamander 300.0
Newt 1000.0
total 1400.0

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?

Recommended Posts

Optimization learned with OR-Tools Part0 [Introduction]
Optimization learned with OR-Tools [Linear programming: multi-stage model]
Optimization learned with OR-Tools [Linear programming: project management]
Optimization learned with OR-Tools [Linear programming: Let's refine oil]
Road installation with optimization
sandbox with neo4j part 10
Introduction to PyQt4 Part 1
Getting Started with Optimization
Introduction to Machine Learning with scikit-learn-From data acquisition to parameter optimization
Solving Mathematical Optimization Model Exercises with Google's OR-Tools (3) Production Optimization Problems
Solve Mathematical Optimization Model Exercises with Google's OR-Tools (4) Solve Number Places
Introduction to Socket API Learned in C Part 2 Client Edition
Image processing with Python (Part 2)
Machine learning learned with Pokemon
Try function optimization with Optuna
Studying Python with freeCodeCamp part1
Bordering images with python Part 1
Scraping with Selenium + Python Part 1
Grouping games with combinatorial optimization
Restore disjointed photos with optimization!
Introduction to RDB with sqlalchemy Ⅰ
Studying Python with freeCodeCamp part2
Introduction to Nonlinear Optimization (I)
Texture analysis learned with pyradiomics
Image processing with Python (Part 1)
Combinatorial optimization with quantum annealing
Solving Sudoku with Python (Part 2)
General-purpose global optimization with Z3
Image processing with Python (Part 3)
Scraping with Selenium + Python Part 2
An introduction to Bayesian optimization
Introduction to Ansible Part ③'Inventory'
Adjust hyperparameters with Bayesian optimization
Introduction to Ansible Part ④'Variable'
Introduction to Socket API Learned in C Part 3 TCP Server / Client # 1
Introduction to Socket API Learned in C Language Part 1 Server Edition
Introduction to Socket API Learned in C Part 4 UDP Server / Client # 1