Linear programming is a powerful Optimization technique that is used to improve decision making in many domains. This is the first part in a multi-part series that will cover important topics having to do with linear programming. This first article will be the most simple and is meant to cover the basics before getting into more advanced linear programming topics.
In this article, we will:
- Discuss what constitutes a linear programming problem
- Go over how linear programming works and why it is powerful
- Run a linear programming example in Python
I personally find examples to be a very effective vehicle for learning technical topics. For that reason, we will be following a simple example throughout this article. I’ll introduce the example in the next section.
Before we dive in, if you aren’t very familiar with the basic concepts and terminology of optimization, I wrote an intro to optimization article that I encourage you to check out before continuing (there are many generic optimization terms in this article that I do not define).
Setting Up Our Example
We are going to follow a silly example to give context to the concepts we’ll cover in this article. We are going to imagine that we are very simple people who only eat two things — apples🍏 and candy bars🍫 . We want to balance our health and our flavor enjoyment. That’s the set-up for our example, in the following sections, I’ll go over linear programming concepts and then apply the to this example. By the end, we’ll have run full optimization to help us decide how many apples and how many candy bars we should eat!
What is Linear Programming?
Linear programming is an optimization technique that minimizes or maximizes a linear objective function subject to constraints in the form of linear equations or inequalities (that’s a lot of jargon, don’t worry, we’ll put it into our intuitive example soon). The name "linear programming" predates what we typically think of as programming now, i.e., computer programming. Linear programming was developed and used in the WWII era. It was widely used to manage operational programs — such as moving supplies from factories to front lines. So, the "programming" refers to planning or scheduling rather than computers. Just a tid-bit of historical context so you aren’t always wondering when the ‘programming’ part comes in!
While it was originally developed to solve operational/logistical problems, there are many clever ways to make linear programming work for a wide array of problem types!
A linear programming problem has 3 parts described below:
Let’s set up these three parts for our apples and candy bars example.
Type: We want to maximize the enjoyment we have from eating food – so it is a maximization problem.
Objective Function: Luckily for us, we know ourselves so well, that we can quantify how much we enjoy apples and candy bars – we have even more luck in that our enjoyment makes a linear function that is perfect for LP problems 😅 !
This function can be used to calculate how much enjoyment we get given how many apples and candy bars we eat. We get 1 unit of enjoyment when we eat an apple, we get 3 units of enjoyment when we eat a candy bar.
Constraints: Although we have very little variety in our diet, we have a little bit of concern regarding our health. We’ve decided that we want to limit our (1) caloric and (2) sugar consumption. Since we want to control two variables, we need two constraints. We need to set up linear functions that will calculate calories and grams of sugar given a number of apples and candy bars. Once we have set up the formulas, we’ll make them inequalities based on how we want to limit our consumption. We’ve decided that we want to eat no more than 850 calories and consume no more than 100 grams of sugar.
Here are our constraints:
Alright, we now have a full linear programming problem set up! Here’s the summary:
We are very lucky that all of our preferences and constraints for food consumption are linear. There are a lot of rules about what types of constraint and objective functions that are allowed for basic linear programming. Violations to the rules are listed below:
LP can be expanded to allow for many of these violations – but allowing for the elements above loses the guarantee that the solution will be a global optimum. For our example today, we will stay within the lines! Future articles will explore how we can violate some of these rules using a modified linear programming framework called Mixed Integer Linear Programming.
How it Works
I think it is easiest to understand how linear programming works by creating a graphical representation. Since we only have two decision variables, we can make nice 2-D graphs (how convenient that we only eat two foods). We start by graphing our constraints:
The orange and blue lines are our linear constraints. We are only accepting solutions that are less than or equal to both of the lines. The shaded region is our feasible solution space. The task of the LP problem is to find the spot in the solution space that maximizes our objective function (our food enjoyment). This can seem like a daunting task — our solution space is infinite (since we can eat fractions of apples and candy bars)! Not to worry though, because all of our functions are linear, we can use a trick to reduce our infinite solution space to a finite set!
Let’s think about our solution space for a little bit. It is the gray area bounded by the blue and orange lines. When looking for optimal solutions, we are looking for extremes — the lowest or highest. So, it makes sense that the optimal solution will be on the borders or the gray area, because that is the most extreme. Now, we can conclude that our optimal solution is somewhere on the border of our feasible space. But that is still an infinite space. We need one more trick to get to a finite solution space. Let’s pick a random point on our blue line:
How can we make this point more extreme while staying on this edge of the feasible region? We could slide it all the way to the edge of the feasible region on the left, or we could slide it to where the orange line intersects with the blue line to the right. After that point, the orange line defines the feasible region instead of the blue line. These points are the most extreme points for this portion of the solution space. If we follow this logic for each edge or the solution space, we find that all of the intersections are the most extreme points of the edges. Through this algorithm, we reduce our infinite solution space to finite by just looking at the corners of the space. If our objective function and constraints are linear, the optimal solution will always be one of the corners! We simply need to look at all of the corner’s objective values and select the point with the highest or lowest value!
Below is a graphical representation of the linear programming algorithm searching for the optimal solution at the corner points:
As we discussed earlier, the objective function and constraints need to be linear for an LP problem. Now that we have a better understanding of how the LP problem works — i.e., checking the corners of the constraints — we are in a good position to understand how linearity violations can cause problems. When non-linear functions are introduced, extreme points can be found between corners because the lines are not monotonically increasing or decreasing. This nullifies the ‘trick’ that LP has of checking the corners to make the potential solution list finite.
In the example below, our calorie constraint is quadratic (of course this makes no practical sense — but let’s just go with it for the example’s sake!). The optimal solution is now the max of the parabola, which is not at a corner. So, if we were to try the corner method on this set of constraints, we would get a suboptimal solution! In summary, the constraints and objectives need to be linear because LP relies on the corners being the extreme points which means that the optimal solution is always at a corner. As we see below, when that doesn’t hold, the ‘trick’ doesn’t guarantee an optimal solution.
Now I’m going to take a few minutes to talk about two scenarios where the LP algorithm will run, but not return an optimal solution. The first is if the solution space that meets all of the constraints is null. For example, if I decided that I wanted to eat negative sugar, there would be no space below the calorie constraint and above 0 for the X and the Y axis. See the graph below as an example. This will result in an ‘infeasible’ result.
The second scenario is when the solution space isn’t fully boxed in by the constraints. Image that instead of eating less than 850 calories and 100 grams of sugar, we wanted to eat at least 850 calories and 100 grams of sugar (meaning we switched our constraints to ≥). Then, our solution space would be unbounded. We could always eat more candy bars and apples and get more enjoyment. Of course this makes no sense! We would get an ‘Unbounded’ result – meaning that a meaningful optimal solution cannot be reached. With those two notes out of the way, let’s solve the LP problem in Python.
Running the Example in Python
Now we are going to get into how we can solve this linear programming problem in Python, using a package called pulp. Before we get into those details, I’ve already written two articles that use linear programming. One article, on simulation, demonstrates tangentially how linear programming can be used to help a fictitious housing developer optimize profit. The other article goes over a distribution comparison metric called the ‘earth mover’s distance’ which uses linear programing in its calculation. Check the links out below to see two more examples of how linear programming can be used!
Okay, let’s get into coding the example we’ve been going through! The coding isn’t too bad.
After importing the pulp package, we instantiate a pulp.LpProblem object — here is where we define if we are solving a maximization or minimization problem.
import pulp
# Create the LP problem
lp_problem = pulp.LpProblem("Apples and Candy Bars", pulp.LpMaximize)With our problem instantiated, let’s use the pulp.LpVariable function to create our decisions variables for apples and candy bars. Note : the lowBound parameter can be set to 0 to add a non-negative constraint to the decision variables.
# Define the decision variables
apples = pulp.LpVariable('apples', lowBound=0)
candy_bars = pulp.LpVariable('candy_bars', lowBound=0)Now, we use the ‘+=’ operator to add our objective function and our constraints to the problem instance. Pulp doesn’t have a parameter to indicate if you are adding an objective function or constraints directly. Instead, it interprets a function that doesn’t have an equality/inequality as the objective functions and functions with equalities/inequalities as constraints. This is a little confusing, but it will hopefully make sense when you look over the code snippet below.
# Add the objective function - level of enjoyment from specific diet
# notice, no equality or inequality at the end of the function
lp_problem += 1 * apples + 3 * candy_bars
# Add calorie constraint
lp_problem += 95 * apples + 215 * candy_bars <= 850
# Add sugar constraint
lp_problem += 15 * apples + 20 * candy_bars <= 100Okay, everything is set up now! All we have to do is call the solve() method on our lp_problem object and print the results!
# Solve the problem
lp_problem.solve()
# Print the results
print(f"Status: {pulp.LpStatus[lp_problem.status]}")
print(f"apples = {pulp.value(apples)}")
print(f"candy bars = {pulp.value(candy_bars)}")
print(f"Objective value = {pulp.value(lp_problem.objective)}")Here are the printed results:
The status of ‘Optimal’ means that an optimal solution has been found — if no feasible solution was found or if it was unbounded, the ‘status’ attribute would indicate that to us. We can see that the optimal solution is to eat 3.95 candy bars and 0 apples for a total enjoyment of 11.86. This is exactly what we found when we solved the problem manually!
Here is the code in a single snippet:
import pulp
# Create the LP problem
lp_problem = pulp.LpProblem("Apples and Candy Bars", pulp.LpMaximize)
# Define the decision variables
apples = pulp.LpVariable('apples', lowBound=0)
candy_bars = pulp.LpVariable('candy_bars', lowBound=0)
# Add the objective function - level of enjoyment from specific diet
lp_problem += 1 * apples + 3 * candy_bars
# Add calorie constraint
lp_problem += 95 * apples + 215 * candy_bars <= 850
# Add sugar constraint
lp_problem += 15 * apples + 20 * candy_bars <= 100
# Solve the problem
lp_problem.solve()
# Print the results
print(f"Status: {pulp.LpStatus[lp_problem.status]}")
print(f"apples = {pulp.value(apples)}")
print(f"candy bars = {pulp.value(candy_bars)}")
print(f"Maximum enjoyment = {pulp.value(lp_problem.objective)}")Conclusion
By now you should have a good understanding of what a LP problem is, how LP problems find optimal values and how to set them up and solve them in Python! In future articles we’ll go over details on how the LP algorithm works to check edges (called the Simplex method) and expansions of the LP problem to include integer variables (instead of just continuous).
