[python] Introduction to pulp
library python
Published : 2020-05-30   Lastmod : 2021-11-15

Python PuLP Mathematical Optimization

I have never done optimization calculations with pulp before, so I’ll try to run through the basic usage of pulp according to the reference article.

The following is the article I used as a reference. It is very easy to understand.

github

  • The file in jupyter notebook format on github is here

google colaboratory

  • To run it in google colaboratory here 008/008_nb.ipynb)

Author’s environment

! sw_vers
ProductName: Mac OS X
ProductName: Mac OS X
ProductVersion: 10.14.6
BuildVersion: 18G6020
Python -V
Python 3.7.3

1. Linear optimization problems (linear programming problems)

I remember doing this in high school math.

maximization

$$ x + y $$ x + y

constraints

$$ 2x + y \leq 2 \\
x + 2y \leq 2 \\
x \geq 0 \\
y \geq 0 $$ $$

import pulp
import sys

# Declare the optimization (maximization)
prob = pulp.LpProblem('test', pulp.LpMaximize)

# Declare the variables
x = pulp.LpVariable("xx", 0, sys.maxsize, pulp.LpContinuous)
y = pulp.LpVariable("yy", 0, sys.maxsize, pulp.LpContinuous)

# Declare the objective function
prob += ( x + y, "Objective" )

# Declare a constraint
prob += ( 2 * x + y <= 2 , "Constraint_1" )
prob += ( x + 2 * y <= 2 , "Constraint_2" )
prob
test:
MAXIMIZE
1*xx + 1*yy + 0
SUBJECT TO
Constraint_1: 2 xx + yy <= 2

Constraint_2: xx + 2 yy <= 2

VARIABLES
xx <= 9.22337203685e+18 Continuous
yy <= 9.22337203685e+18 Continuous
result = prob.solve()
print("Result")
print("*" * 8)
print(f "Optimality = {pulp.LpStatus[result]}")
print(f "Objective function value = {pulp.value(prob.objective)}")
print(f "solution x = {pulp.value(x)}")
print(f" y = {pulp.value(y)}")
print("*" * 8)
Calculation results
********
Optimality = Optimal
Objective function value = 1.333333334
Solution x = 0.6666666667
  y = 0.66666666667
********

2. Integer optimization problem (integer programming problem)

minimization

$$ \sum_{i \in I} \sum_{j \in J} c_{ij}x_{ij} $$

Constraints

$$ \sum_{j\in J}x_{ij} \leq 1 \\
\sum_{i\in I}x_{ij} = 1 \\
x_{ij} \in {0,1} $$

import pulp
import time

# Set of workers (for convenience, we use a list)
I = ["Mr. A", "Mr. B", "Mr. C"].

print(f "Set of workers I = {I}")

# Set of tasks (for convenience, use a list)
J = ["Task A", "Task B", "Task C"].

print(f "Set of tasks J = {J}")

# Set of costs for assigning worker i to task j (temporary list)
cc = [.
    [ 1, 2, 3],
    [ 4, 6, 8],
    [10, 13, 16],
   ]

# Since cc is a list and the subscripts are numeric.
# Define a dictionary c so that, for example, cc[0][0] can be accessed by c["Mr. A", "Job I"].
c = {} # empty dictionary
for i in I:
  for j in J:
    c[i,j] = cc[I.index(i)][J.index(j)].

print("Cost c[i,j]: ")
for i in I:
  for j in J:
    print(f "c[{i},{j}] = {c[i,j]:2d}, ", end = "")
  print("")
print("")
Set of workers I = ['Mr. A', 'Mr. B', 'Mr. C'].
Set of tasks J = ['Task A', 'Task B', 'Task C'].
Cost c[i,j]: 
c[Mr. A,Task i] = 1, c[Mr. A,Task b] = 2, c[Mr. A,Task c] = 3,  
c[Ms. B,Work A] = 4, c[Ms. B,Work B] = 6, c[Ms. B,Work C] = 8,  
c[Mr. C, Job A] = 10, c[Mr. C, Job B] = 13, c[Mr. C, Job C] = 16,  
# Declare mathematical optimization.
# pulp.LpMinimize => Minimize
# pulp.LpMaximize => maximize

prob = pulp.LpProblem('prob', pulp.LpMinimize)
# Dictionary for a set of variables
x = {} # empty dictionary
     # Read and write values in x[i,j] or x[(i,j)], using the tuple (i,j) as key

# Declare a 0-1 variable
for i in I:
  for j in J:
    x[i,j] = pulp.LpVariable(f "x({i},{j})", 0, 1, pulp.LpInteger)
    # Why does the variable label change to '_' when I put '[', ']' or '-'?
# If lowBound and upBound are not specified, they become -infinity and +infinity respectively.

# You can also use comprehension notation.
# x_suffixes = [(i,j) for i in I for j in J].
# LpVariable.dicts("x", x_suffixes, cat = pulp.LpBinary) 

# LpContinuous : continuous variable
# LpInteger : Integer variable
# LpBinary : 0-1 variable
# Declare the objective function
prob += pulp.lpSum(c[i,j] * x[i,j] for i in I for j in J), "TotalCost"
# problem += sum(c[i,j] * x[i,j] for i in I for j in J)
# Declare constraints
for i in I:
  prob += sum(x[i,j] for j in J) <= 1, f "Constraint_leq_{i}"
  # If I put '[' or ']' or '-' in the constraint label, why does it change to '_'...?

# For each task j, there is exactly one worker to assign
for j in J:
  prob += sum(x[i,j] for i in I) == 1, f "Constraint_eq_{j}"
# Print the whole expression of the problem
print("Expression in question")
print(f"-" * 8)
print(prob)
print(f"-" * 8)
print("")
The expression in question
--------
prob:
MINIMIZE
1*x(Mr. A, Job A) + 3*x(Mr. A, Job C) + 2*x(Mr. A, Job B) + 4*x(Mr. B, Job I) + 8*x(Mr. B, Job C) + 6*x(Mr. B, Job B) + 10*x(Mr. C, Job I) + 16*x(Mr. C, Job C) + 13*x(Mr. C, Job B) + 0
SUBJECT TO
Constraint_leq_A: x(Mr. A,Job A) + x(Mr. A,Job C) + x(Mr. A,Job B) <= 1

Constraint_leq_B: x(Mr. B, Job A) + x(Mr. B, Job C) + x(Mr. B, Job B) <= 1

Constraint_leq_C: x(Mr. C,Job A) + x(Mr. C,Job C) + x(Mr. C,Job B) <= 1

Constraint_eq_work_i: x(Ms A,work_i) + x(Ms B,work_i) + x(Ms C,work_i) = 1

Constraint_eq_Work_R: x(Mr. A,Work_R) + x(Mr. B,Work_R) + x(Mr. C,Work_R) = 1

Constraint_eq_Job_H: x(A,Job_H) + x(B,Job_H) + x(C,Job_H) = 1

VARIABLES
0 <= x(Ms. A,Job I) <= 1 Integer
0 <= x(Ms. A,Job C) <= 1 Integer
0 <= x(Mr. A, Job B) <= 1 Integer
0 <= x(Mr. B, Job A) <= 1 Integer
0 <= x(Ms. B, Job C) <= 1 Integer
0 <= x(Mr. B, Job B) <= 1 Integer
0 <= x(Ms. C, Job A) <= 1 Integer
0 <= x(Ms. C, Job C) <= 1 Integer
0 <= x(Mr. C, Job B) <= 1 Integer

--------
# Compute
# Solver specification
solver = pulp.PULP_CBC_CMD()
# pulp.PULP_CBC_CMD() : Coin-CBC that comes with PuLP
# pulp.GUROBI_CMD() : Start Gurobi from command line (.lp file is created temporarily)
# GUROBI() : Launch Gurobi from the library (need to specify the location of the library)

# Start time measurement
time_start = time.perf_counter()

result_status = prob.solve(solver)
# Solver can be specified in () of solve().
# If nothing is specified, pulp.PULP_CBC_CMD()

# End of time measurement
time_stop = time.perf_counter()
# Print the objective function value and solution (if the solution was obtained)
print("Calculation result")
print(f "*" * 8)
print(f "Optimality = {pulp.LpStatus[result_status]}, ", end="")
print(f "objective function value = {pulp.value(prob.objective)}, ", end="")
print(f "Computation time = {time_stop - time_start:.3f} (in seconds)")
print("Solution x[i,j]: ")
for i in I:
  for j in J:
    print(f"{x[i,j].name} = {x[i,j].value()}, ", end="")
  print("")
print(f "*" * 8)
Calculation results
********
Optimality = Optimal, Objective function value = 19.0, Computation time = 0.028 (sec)
Solution x[i,j]: 
x(Mr. A,Job a) = 0.0, x(Mr. A,Job b) = 0.0, x(Mr. A,Job c) = 1.0,  
x(Ms. B, job a) = 0.0, x(Ms. B, job b) = 1.0, x(Ms. B, job c) = 0.0,  
x(Ms. C, job a) = 1.0, x(Ms. C, job b) = 0.0, x(Ms. C, job c) = 0.0,  
********

I learned a lot, line by line. Please jump to the link and study it in the original article.

Related Articles