Linear Programming using Python

Created date: 2020 Jul 27, Mon

Reading time ~3 minutes

Linear programming

Linear programming is a group of mathematical and computational tools that allows to find a solution (or a optimal solution) to a this system that corresponds to a optimum of a linear functions.

Linear programming using Python

Let’s start with a question.

Consider the following transporting problem:

There are m plants that produce amounts s1, s2, …, sm, of a commodity daily
There are n locations that require amounts t1, t2, …, tn of the commodity daily
Transporting one unit of commodity from plant i to location j costs c_{ij}

We want to minimize shipping costs while still supplying the required amounts of commodity of each location.

Mathematical formulation: suppose we ship amount of X_{ij} of the commodity from plant i to location j.

Mimimize \(\sum_{i=1}^{m} \sum{j=1} C_{i,j} x_{i,j} \)

Subject to (Constraints)

\(\sum_{j=1}^n x_{i,j} \le s_{i} \) for i = 1 to m (only ship what we can produce)
\(\sum_{i=1}^m x_{i,j} \ge t_{j} \) for j = 1 to n (each location gets enough)
\(x_{i,j}\) for i = 1 to m, j = 1 to n (cant ship negative amount)

A detail example is shown below. Suppose we have

two plants s1 = 35, s2, = 31
three locations that need t1 = 26, t2 = 20, t3 = 17
the cost of transporting one unit from plant i to location j is given by

-	loc1	loc2	loc3
plant1	8	13	6
plant2	9	12	7

To solve this question, I will use PuLP which is a Python linear programming API for defining problems.

#!/usr/bin/env python
# encoding: utf-8
from pulp import *

# step1. Define the problem 
# Here we want to minimize the costs, thus applying `LpMinimize`.
# We can choose whether to perform minimization 
# (LpMinimize or 1, which is the default) or maximization (LpMaximize or -1).
prob = LpProblem("Commodity", LpMinimize)


# step2. Define decision variable 
# We need to provide a lower bound with lowBound=0 
# because the default value is negative infinity.
variables = [ "x11", "x12", "x13", "x21", "x22", "x23" ]
vars_dict = LpVariable.dicts("FromPlantToLocation", variables, lowBound=0)


# step3. Add the objective function. 
costs = { "x11": 8, "x12": 13, "x13": 6, "x21": 9, "x22": 12, "x23": 7 }
prob += lpSum([costs[i] * vars_dict[i] for i in variables])

# step4. Add constraints 

# plant constraints
prob += (lpSum([vars_dict["x11"], vars_dict["x12"], vars_dict["x13"]]) <= 35, \
         'ship what we can produce at plant1')
prob += (lpSum([vars_dict["x21"], vars_dict["x22"], vars_dict["x23"]]) <= 31, \
         'ship what we can produce at plant2')

# locations constraints 
prob += (lpSum([vars_dict["x11"], vars_dict["x21"]]) >= 26,\
         'the amount location1 should get at least')
prob += (lpSum([vars_dict["x12"], vars_dict["x22"]]) >= 20,\
         'the amount location2 should get at least')
prob += (lpSum([vars_dict["x13"], vars_dict["x23"]]) >= 17,\
         'the amount location3 should get at least')
         
# step5. Solve 
status = prob.solve()
print(f"status: {prob.status}, {LpStatus[prob.status]}")
print(f"objective: {prob.objective.value()}")
for var in prob.variables():
    print(f"{var.name}: {var.value()}")
for name, constraint in prob.constraints.items():
    print(f"{name}: {constraint.value()}")

output:
>>>
status: 1, Optimal
objective: 558.0
FromPlantToLocation_x11: 18.0
FromPlantToLocation_x12: 0.0
FromPlantToLocation_x13: 17.0
FromPlantToLocation_x21: 8.0
FromPlantToLocation_x22: 20.0
FromPlantToLocation_x23: 0.0
ship_what_we_can_produce_at_plant1: 0.0
ship_what_we_can_produce_at_plant2: -3.0
the_amount_location1_should_get_at_least: 0.0
the_amount_location2_should_get_at_least: 0.0
the_amount_location3_should_get_at_least: 0.0