Linear Programming with Python

In the field of data science, often we can find optimization problems (such as maximizing profit or minimizing cost). In this post I will demonstrate solving an imaginary mathematics problem— maximizing the happiness delivered by Santa Claus, by using PuLP with Python.

from pulp import *

Problem

Santa is going to deliver presents (limited to three types only to make it simple), and each will generate a fixed happiness point. The table below summarizes the attributes of the presents.

Our objective function is to maximize total happiness points:

Maximize: 100x1 + 20x2 + 5x3

We first define a LpProblem as a maximization one by LpMaximize, followed by the objective function.

# Create the 'prob' variable to contain the problem data
prob = LpProblem("The Santa Problem", LpMaximize)

# The objective function is added to 'prob' first

prob += 100*x1 + 20*x2 + 5*x3, "Total happinesss"

Variables

Santa can only deliver whole number (e.g., 0, 1, 2, …) of presents:

x1≥0, x2≥0, x3≥0

We then define for each present type a LpVariable, and specify the lower bound as 0, upper bound as None (unlimited) and category as LpInteger.

# Define the variables, lower bound, upper bound and category

x1 = LpVariable("console", 0, None, LpInteger)
x2 = LpVariable("bear", 0, None, LpInteger)

x3 = LpVariable("candy", 0, None, LpInteger)

Constraints

However, there are certain limitations (usually in terms of money, quantity, and other metrics):

1. Santa can spend at most $900 in this year
2. The reindeers can carry at most 100lb of presents
3. Deliver at least 50 presents
4. At least 5% are game consoles
5. At least 10% are teddy bears

We add all constraints to the LpProblem

prob += 150*x1 + 30*x2 + 5*x3 <= 900, "MaxBudget"
prob += 10*x1 + 3*x2 + x3 <= 100, "MaxWeight"
prob += x1 + x2 + x3 >= 50, "NumPresents"
prob += x1 >= 0.05*(x1+x2+x3), "MinConsole"

prob += x2 >= 0.1*(x1+x2+x3), "MinBear"

Solution

And finally pass the problem to the solver, and display the results.

# The problem is solved using PuLP's choice of Solver
prob.solve()

# Solution status
print("Status:", LpStatus[prob.status])

# Variables
for v in prob.variables():

print(v.name, "=", v.varValue)

• Status: Optimal
• bear = 7.0
• candy = 48.0
• console = 3.0

To maximize happiness delivered, Santa should deliver 3 game consoles, 7 teddy bears and 48 boxes of candy.

# Shadow price / Slack
for name, c in prob.constraints.items():
print(name, c.pi, c.slack)

# Objective

print('Total happiness = ', value(prob.objective))

MaxBudget -0.0 -0.0

MaxWeight -0.0 1.0

NumPresents -0.0 -8.0

MinConsole -0.0 -0.1

MinBear -0.0 -1.2

Total happiness = 680.0

With that combination,

• Santa will spend all of the budget
• Reindeers will carry 1lb less than maximum limit
• 8 more children (than the minimum requirement) will receive presents
• Total happiness points delivered: 680