Memorandum @ Python OR Seminar: Pulp

Library for mathematical optimization modeling. Solvers such as Gurobi, CBC, and GLPK can be used. I don't know much about optimization, so I plan to study in the future.

Mathematical model creation procedure

The procedure for solving a problem with a mathematical model is as follows.

• () Is the class name in pulp.

1. Create a mathematical model (LpProblem)
2. Add a variable (LpVariable)
3. Add the objective function expression (LpAffineExpression)
4. Add a constraint (LpConstraint)

Mathematical model: LpProblem

LpProblem(name='NoName', sense=LpMinimize)

--name: Mathematical model name. Default is NoName. --sense: Either minimize (LpMinimize) or maximize (LpMaximize).

Variable: LpVariable

LpVariable(name, lowBound=None, upBound=None, cat='Continuous', e=None)

--name: Variable name -- lowBound: Lower limit --ʻUpBound: Upper limit --cat`: Variable type

• LpContinuous: Continuous variable
• LpInteger: Integer variable
• LpBinary: Binary variables
• ʻE`: Used for column-based model (not sure)

Objective function: LpAffineExpression

Can be created like " x + 2 * y "using variables It is also possible to add terms to the expression later Specify the objective function as "m + = expression" (however, m is a mathematical model)

Constraint: LpConstraint

Can be created like " x + y <= 1 "using variables It is also possible to add a term later on the left side of the constraint Constraints are specified as " m + = expression <= right side "

Other

Functions that seem to be used often value (): Fetch the value of a variable lpSum (): Find the sum of terms lpDot (): Find the dot product of two lists

The cheat sheet is here

Try to solve the knapsack problem

Common optimization problems

Put as many items as possible in a knapsack then:

--The maximum weight that can be put in a knapsack is 600 grams.

There are restrictions like. So what do you do?

Formulate

Insert the item $ s_i $ → $ v_i = 1 $ Do not put item $ s_i $ → $ v_i = 0 $

\begin{array}{cl}
\max & \sum_i{s_i \ v_i} \\
\mbox{subject to} & \sum_i{s_i \ v_i} \leq C \\
                 & v_i \in \{0, 1\} ~ \forall i
\end{array}

Implement with pulp

>>> #The weight of the item
>>> s = [128, 108, 34, 53, 71, 224, 299, 181, 336, 15]
>>> #Maximum load capacity of knapsack
>>> C = 600
>>> #Library preparation
>>> from pulp import LpProblem, LpVariable, LpMaximize, LpBinary
>>> rn = range(len(s))
>>> #Model preparation
>>> m = LpProblem('knapsack', LpMaximize)
>>> #variable(0 whether to include the i-th item/1)
>>> v = [LpVariable('v%d' % i, cat = LpBinary) for i in rn]
>>> #Objective function
>>> m += lpDot(s, v)
>>> #Constraint
>>> m += lpDot(s, v) <= C
>>> #solve
>>> m.solve()
>>> #output
>>> print(LpStatus[m.status], sum(s[i] * value(v[i]) for i in rn))
>>> print([s[i] for i in rn if value(v[i]) > 0.5])
Optimal 600.0
[108, 34, 53, 224, 181]

Other optimization problems

Other optimization problems can be solved by formulating (like)

Facility placement problem (p-median)

The problem of selecting p from the facility candidates and minimizing the total distance from the demand point to the facility

Example

• Select 4 evacuation centers from the evacuation center candidates and minimize the total distance traveled from the residents to the evacuation centers (p == 4)
• $ x_ {ij} $ indicates whether the resident j evacuates to facility i, and $ y_i $ indicates whether or not facility i is selected (distance is $ d_ {ij} $).

Formulation

\begin{array}{cl}
\min & \sum_i{\sum_j{d_{ij} \ x_{ij}}} ~ ~ ~ ~ (1) \\
\mbox{subject to} & \sum_i{y_i} = p ~ ~ ~ ~ (2) \\
                 & \sum_i{x_{ij}} = 1 ~ \forall j ~ ~ ~ ~ (3) \\
                 & x_{ij} \leq y_i ~ \forall i, j ~ ~ ~ ~ (4) \\
                 & x_{ij} \in \{0, 1\} ~ \forall i, j
\end{array}

Sudoku

That is common.

• Do not set the objective function as long as the constraints are met
• A 0/1 variable indicates whether to use the number k at the position of row i and column j.
• represented by v [i, j, k]
• Constraints
• Only one number can be used at the vertical i and horizontal j positions (1)
• Only one number j can be used in each line i (2)
• Only one number j can be used in each column i (3)
• Only one number j can be used in 3 $ \ times $ 3 (4)

Formulation

\begin{array}{cl}
\min & \mbox{no objective function} \\
\mbox{subject to} & \sum_k{v_{ijk}} = 1 ~ \forall i, j ~ (1)\\
                 & \sum_k{v_{ikj}} = 1 ~ \forall i, j ~ (2) \\
                 & \sum_k{v_{kij}} = 1 ~ \forall i, j ~ (3) \\
                 & 3\The same applies to the squares of times3~ (4) \\
                 & v_{ijk} \in \{0, 1\} ~ \forall i, j, k
\end{array}

Other optimization problems