Explanation of production optimization model by Python

Introduction

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.

Target person

--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

Target 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

Python code

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

Commentary

Package specification

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".

Reading input table

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.

Splitting the input table

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).

Creating a model

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.

Add a column of variables

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".

Add objective function

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.

Add constraints

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 "! =".

Solver execution

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.

Add result

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'] =…".

View results

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.

Other

――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) $.

To study

--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!