How to Create Your First Linear Programming Solver in Python

---

Linear Programming

Linear Programming (LP) is a method to get to an optimal solution of a problem by solving a linear equation.

Ok, still a puzzle to you? Then let me try to simplify even more.

Linear Programming will look to a problem and transform it in a mathematical equation using variables like x and y. After that, it is a matter of trying numbers for those variables until you reach the best solution, what can be the maximum or minimum possible value.

If I give you the equation x + y = 10 and ask for the maximum value of x, that is a good example of LP.

It is called Linear because those xy-like mathematical expressions can be represented as a line in space, meaning that if I solve the equation by finding the values of x and y and plot the resulting combination on a 2-dimensional graphic, the result will be a line.

Explaining the Concepts

In this section, my intention is to apply the Linear Programming to a very simple problem, what will give us a full understanding of how to translate our problem into an equation, how the linear solvers work and how to program them.

First things first. Before the coding, let’s go over a few concepts.

• Objective Function: that is the goal, the problem you are actually trying to solve (e.g. maximize profit, minimize loss, optimize space allocation).
• Constraints: the can’s and cant’s. What can or cannot not happen while you’re solving the problem (e.g. value can’t be negative, max space available in a container).
• Variables: the variable parts of your problem (e.g. products, prices, profit, size).

Solvers

There are a couple of LP solvers packages available in Python. Among them are SciPy, PuLP, CVXOPT. In this tutorial, we’re working with PuLP.

Install it using pip:

pip install pulp 

# for Jupyter Notebooks
!pip install pulp

The Problem

Imagine we have a square field of 100 meters by 100 meters where we must draw the longest 45 degrees diagonal line starting at point 0 up to the upper right corner. However, let’s imagine that there is a fence 5 meters away from the upper margin and another fence 5 meters away from the right margin. I want to know what is my maximum value of X and Y (my coordinates to draw the longest line) if I have to stop at the fence.

Like I said, this is a very simple problem. You probably figured it out by yourself that the answer is x=95 and y=95, right? And that is also part of my method here. Now that you already know the answer, let’s work on the logic we can build to make the computer get to the result.

Objective Function

Like previously mentioned, the objective function is our goal, what we want to accomplish, what we’re trying to solve.

The objective function is what we are trying to solve.

In our example here, we want to draw a diagonal line. Do you agree with me that, in order to draw a diagonal on a 2D graphic, all we have to do is to assign the same value to X and Y?

Also, we want to add values up to a maximum. Thus, our objective function becomes x + y.

Constraints

We have only two simple constraints in this problem: the line can’t go after the fence and the values can’t be negative.

Constraints are the rules that the objective function must follow.

Now to put that constraint in a mathematical form, we must use x and y again. Let’s think logically. If the field is 100 x 100 and we have a fence 5 meters from top and 5 meters from right, we should say that x can’t be higher than 100–5 (a.k.a 95). The same applies to y, as this would mean that the line went over the fence.

1. 0 ≤ x ≤ 95
2. 0≤ y ≤ 95

Creating the Solver

The next step is using PuLP to create our solver and find the maximum coordinates values for the end of the diagonal line.

Import the modules to your Python session:

from pulp import LpMaximize, LpProblem, LpStatus, LpVariable

Create an instance of the solver and the variables. Notice that the lowBoundparameter here will act as a constraint to prevent negative values. The upBound parameter is not that important, given that it will be overwritten by the fence constraint, but still nice to know it’s there.

# Create the maximization problem
model = LpProblem(name='Field Problem', sense=LpMaximize)

# Initialize the variables
x = LpVariable(name="x", lowBound=0, upBound=100)
y = LpVariable(name="y", lowBound=0, upBound=100)

Next step is to add the constraints to the model. The first element is a LpConstraint instance. The second element is a name you want to give for that constraint. We could create the x≥0 and y≥0, but that is already taken care, as explained before.

# Add the constraints to the model. Use += to append expressions to the model

model += (x <= 95, "margin_X") #it cannot go past the fence
model += (y <= 95, "margin_Y")

Now we add the objective function to the model.

# Objective Function
obj_func = x + y

# Add Objective function to the model
model += obj_func

If you’d like to see the model just created prior to solve it, just call your model name. There you will see how it reads the problem logically as a math problem. Maximize function x+y subject to x and Y being less than 95.

model

Field_Problem: 
MAXIMIZE 
1*x + 1*y + 0 
SUBJECT TO 
margin_X: x <= 95  
margin_Y: y <= 95 

VARIABLES 
x <= 100 Continuous 
y <= 100 Continuous

Solve.

status = model.solve()

Print a report.

print(f"status: {model.status}, {LpStatus[model.status]}")
print(f"objective: {model.objective.value()}")
for var in model.variables():
    print(f"{var.name}: {var.value()}")

for name, constraint in model.constraints.items():
    print(f"{name}: {constraint.value()}")

[OUT]:
status: 1, Optimal 
objective: 190.0 
x: 95.0 
y: 95.0 
margin_X: 0.0 
margin_Y: 0.0

As expected, the maximum value for x and y is 95.

# The field solution plot

# Create a plot space
plt.figure(figsize=(8,8))

# Dimensions of the field.
xlimits=[0,100,0,100]
ylimits=[0,0,100,100]

# Plot field
plt.scatter(xlimits,ylimits)
# Plot line SOLUTION
plt.plot([0,x.value()], [0,y.value()], c='red')
# Plot MAX POINT
plt.scatter(x.value(),y.value(), c='red')
# Plot Fence 1
plt.vlines(95, 0,100, linestyles='--', colors='red')
# Plot Fence 2
plt.hlines(95, 0,100, linestyles='--', colors='red')

# Annotations
plt.annotate(f'Optimal Value: {x.value(), y.value()} --->', xy=(47, 96));

Before You Go

The intention of this post was to give you a gentle and user-friendly introduction to Linear Programming in Python. The example is extremely simple, but the idea is to build from here, understanding the basic concept to be able to apply that on more complex problems.

Here is a good tutorial from Real Python, if you’d like to go deeper.

Hands-On Linear Programming: Optimization With Python – Real Python

If this content is useful to you, follow my blog.

gustavorsantos