The purpose here is to help ** those who are just starting to optimize with Python to deepen their understanding **.
For information on combinatorial optimization, see “Use Combinatorial Optimization”. We will proceed based on the fact that there are elements such as models, variables, objective functions, and constraints.
--People who want to learn optimization with Python --People who have performed linear optimization with Excel solver etc. --People who want to use the solver for free --People who want to see a template of a typical optimization problem
Production optimization problem I want to maximize profits by producing products with limited raw materials
For details, see [Google Search](https://www.google.co.jp/search?q=Production Planning Problem + Example).
This time, it is assumed that the original input data is prepared in the table below.
data.csv
,Ingredient 1,Ingredient 2,Ingredient 3,Profit
Product 1,1,4,3,5
Product 2,2,4,1,4
stock,40,80,50
python3
import pandas as pd
from pulp import *
from ortoolpy import addvars
Input table= pd.read_csv('data.csv', encoding='cp932', index_col=0) #Reading specifications
Variable table,stock=Input table.iloc[:-1,:].copy(),Input table.iloc[-1,:-1] #Divide into two
model= LpProblem(sense=LpMaximize) #Linear optimization model
Variable table['variable'] = addvars(len(Variable table)) # 生産量を表すvariableを表に追加
model+= lpDot(Variable table.Profit,Variable table.variable) # 総Profitを表す目的関数
for raw material in variable table.columns[:-2]: #Processing for each product
model+= lpDot(Variable table[material],Variable table.variable) <=stock[material] # materialの使用量が在庫以下
model.solve() #Find a solution with the solver
Variable table['result'] = Variable table.variable.apply(value) # variableの値(result)To the table
print('Objective function',value(model.objective)) # Objective functionの表示
print(Variable table) # Variable tableの表示
result
Objective function 95.0
Ingredient 1 Ingredient 2 Ingredient 3 Profit Variable Result
Product 1 1 4 3 5.0 v0001 15.0
Product 2 2 4 1 4.0 v0002 5.0
python3
import pandas as pd
from pulp import *
from ortoolpy import addvars
Import the package you want to use. The variables in the model are represented as columns in the variable table.
--pandas: Used to work with models through variable tables. --When using Anaconda You can use pandas as it is. If not, you can install it with "pip install pandas". --pulp: You can create a mathematical optimization model. --ortoolpy: Use the variable generation function (addvars). --You can also use pulp.LpVariable without using this package. --These two can be installed with "pip install pulp or toolpy".
python3
Input table= pd.read_csv('data.csv', encoding='cp932', index_col=0) #Reading specifications
If the file cannot be prepared
from io import StringIO
Input table= pd.read_table(StringIO("""
Ingredient 1 Ingredient 2 Ingredient 3 Profit
Product 1 1 4 3 5
Product 2 2 4 1 4
In stock 40 80 50
"""),index_col=0)
Read the necessary specifications from the file and use it as an input table. You can easily read it using pandas.read_csv.
python3
Variable table,stock=Input table.iloc[:-1,:].copy(),Input table.iloc[-1,:-1] #Divide into two
Substitute the blue part in the above figure for "Variable table" and the green part for "Inventory". You can use slices in the input table .iloc to retrieve them freely from the table.
For more information on slicing, see [Google Search](https://www.google.co.jp/search?q=python+numpy+ Slice).
python3
model= LpProblem(sense=LpMaximize) #Optimization model
Create an optimization model [^ 1] using pulp.LpProblem. Indicates that you want to maximize the objective function by specifying sense = LpMaximize. If nothing is specified, it will be minimized.
[^ 1]: For practitioners, the state (problem) that they want to solve and the model that abstracts it to make it easier to solve should be properly separated. Researchers often think of the problem as a model because it starts with a formalized one. LpProblem corresponds to the model.
python3
Variable table['variable'] = addvars(len(Variable table)) # 生産量を表すvariableを表に追加
In pandas, you can add a new column named "Variable" in the "Variable Table ['Variable'] =…". addvars allows you to create an array of variables. One row in the variable table corresponds to "1 variable and its attributes".
python3
model+= lpDot(Variable table.Profit,Variable table.variable) # 総Profitを表す目的関数
In pulp, you can set the objective function with "model + =…" [^ 2]. lpDot (c, x) means the inner product, which is $ c ^ T x $.
[^ 2]: It's confusing, but it's not an addition. Even if you do it twice, only the second one is valid.
python3
for raw material in variable table.columns[:-2]: #Processing for each product
model+= lpDot(Variable table[material],Variable table.variable) <=stock[material] # materialの使用量が在庫以下
With pulp, you can add constraints with "model + =… <= value". Alternatively, you can use "> =" and "==", but not "! =".
python3
model.solve() #Find a solution with the solver
The created model can be solved by another program called the solver. With pulp, you can specify various solvers. If nothing is specified, it will be solved using a free solver called CBC. CBC is installed with the pulp installation.
python3
Variable table['result'] = Variable table.variable.apply(value) # variableの値(result)To the table
When solved with the solver, value (XXX) can be used to retrieve the value of XXX. You can apply value to the entire column of variables by doing "Variable table.Variable.apply (value)". A new column of results is created by "Variable table ['Result'] =…".
python3
print('Objective function',value(model.objective)) # Objective functionの表示
print(Variable table) # Variable tableの表示
Results reposted
Objective function 95.0
Ingredient 1 Ingredient 2 Ingredient 3 Profit Variable Result
Product 1 1 4 3 5.0 v0001 15.0
Product 2 2 4 1 4.0 v0002 5.0
If you make 15 for product 1 and 5 for product 2, you will find that the total profit is the maximum of 95.
――For environment construction, Anaconda is convenient. -Using Jupyter Notebook will speed up trial and error. --Use lpSum instead of sum for the sum of expressions. lpSum is $ \ mathcal {O} (n) $, while sum is $ \ mathcal {O} (n ^ 2) $.
--Read a book or look it up on the web. --Participate in study sessions and introductory seminars. --Ask a detailed person. ――I decided to use it at work and drive myself.
Let's enjoy Mathematical Optimization!
Recommended Posts