Linear Programming: Auxiliary Variables
Auxiliary variables seem to be a topic that is often quickly rushed over in a lot of Linear Programming material. I think they are fascinating and quite powerful. Because of this, I decided to dedicate a short article to explaining and demonstrating how auxiliary variables are often used in linear programming.
Before we dive into auxiliary variables – I wanted to mention that this is the fifth part in a series I'm writing on linear programming (LP). To check out the other LP topics I've covered, use the link below:
First of all, let's address the question – what is an auxiliary variable? My definition of an auxiliary variable(in the context of LP) is ‘additional variables that are added to a linear programming problem, that allow the use of logic that otherwise would not be possible.'
Auxiliary Variable: Additional variables that are added to a linear programming problem that allow the use of logic that otherwise would not be possible.
Generally, auxiliary variables are used in clever ways to formulate non-linear relationships (typically a violation of the rules of linear programming) in the objective function and constraints in a way that still works for linear programming. In other words, they allow for linearization of functions that would be non-linear without them. Since there are multiple ways to use auxiliary variables, in this article, we'll go over the most common ways I've seen. My goal is for you to have a good intuition on what auxiliary variables do and how you can use them in linear programming. The rest of the article will go through specific applications of auxiliary variables with detailed examples for each application. Note that this is not meant to be an exhaustive representation of how auxiliary variables are used in linear programming. It is meant to demonstrate some of the most common ways they are used.
Creating Piecewise Linear Functions
The jumps that happen in piecewise linear equations are a ‘no-no' in linear programming. Thankfully, we can accomplish the equivalent of piecewise functions using auxiliary variables! Let's get into an example.
Let's imagine that you manage a manufacturing facility. You need to produce a minimum number of products while minimizing your company's wage expenses. Each employee has an hourly wage and an hourly production rate. Your goal is to create a work schedule that minimizes wage expenses while meeting a specific number of units produced. Easy enough? There's a catch! Any employee that works over 20 hours a week becomes eligible for benefits – these benefits will cost an extra $500 per employee. This represents a jump in the function with the same slope (hourly salary).
We will first explore how to perform an intercept jump. Let's set up the simple problem without the intercept jump, then we can add the complexity of the extra benefits cost at 20 hours of work. In our simple example, we have three employees, they each have a different pay and a different level of productivity (shown in the table below). Our goal is to minimize labor costs while producing at least 600 units a week.
Before the additional complexity of the benefits expense, our objective function and constraint look like this:
Alright, with the LP 101 problem set up, let's get into adding that intercept jump at 20 hours. We are going to use something called the ‘Big-M Method' to do this. In this method, we create one or more binary auxiliary variables and we create an additional constraint to bind the auxiliary variable to the original decision variables. The ‘M' part of ‘Big-M' comes into play in the constraint configuration.
Below is an example of the new constraint we will add – y is the binary auxiliary variable that we added to the problem and M is an arbitrarily large number.
Let's break the constraint down since this is the main concept of performing the jump. On the left we have the decision variable for the hours we will schedule employee 1. On the right, we have the number of hours after which benefits are required plus ‘M' which is an arbitrarily large number (hence _big-_M) and y1 is our binary auxiliary variable. In our example, I'll set M to be 1,000. Understanding this constraint is key! Let's build our intuition by running different values through the inequality for employee 1 hours. See the table and explanations below:
In addition to the new constraint, we also have to make modifications to our objective function. This is pretty simple to do, we add the product of our new auxiliary variables (remember, they are binary) and the intercept jump, in this case $500, to the objective function. When the auxiliary variable is 0, no additional cost is added. When the employee works more than 20 hours, the auxiliary variable is forced to be 1 and $500 is added to the objective value for that employee.
With the problem fully formulated, let's set it up and solve it in Python using the pulp package!
import pulp
# Define the problem
problem = pulp.LpProblem("Staff_Management", pulp.LpMinimize)
# Define the decision variables as integers
empl1 = pulp.LpVariable("empl1", lowBound=0, upBound=60)
empl2 = pulp.LpVariable("empl2", lowBound=0, upBound=60)
empl3 = pulp.LpVariable("empl3", lowBound=0, upBound=60)
# establish employee pay and productivity
empl1_pay = 15
empl2_pay = 18
empl3_pay = 22
empl1_prod = 7
empl2_prod = 8
empl3_prod = 10
# create auxiliary variables to capture piecewise OT function
empl1 = pulp.LpVariable("empl1_reg", lowBound=0, upBound=40)
empl2 = pulp.LpVariable("empl2_reg", lowBound=0, upBound=40)
empl3 = pulp.LpVariable("empl3_reg", lowBound=0, upBound=40)
# add auxiliary variables
y1 = pulp.LpVariable("y1", lowBound=0, cat="Integer")
y2 = pulp.LpVariable("y2", lowBound=0, cat="Integer")
y3 = pulp.LpVariable("y3", lowBound=0, cat="Integer")
# Objective function
problem += empl1_pay*empl1 + 500*y1 + empl2_pay*empl2 + 500*y2 + empl3_pay*empl3 + 500*y3 , "Salary Cost"
# Constraints
# force ret and ot hours to add up to total hours
M = 1000
# big M method
problem += empl1 <= 20 + M*y1
problem += empl2 <= 20 + M*y2
problem += empl3 <= 20 + M*y3
problem += (empl1_prod * empl1 +
empl2_prod * empl2 +
empl3_prod * empl3 >= 600)
# Solve the problem
status = problem.solve()
# Output the results
print(f"Status: {pulp.LpStatus[status]}")
print(f"Optimal value of empl1: {empl1.varValue}")
print(f"Optimal value of empl2: {empl2.varValue}")
print(f"Optimal value of empl3: {empl3.varValue}")
print(f"Minimized salary cost: {pulp.value(problem.objective)}")And here are the results of the run, looks like we can make 600 widgets while incurring $1,810 dollars in labor expenses. Employee 1 will be the only employee to receive benefits (employee 2 is just below the threshold of more than 20 hours).
Alright, now that we've tackled the issue of the additional benefits expense, let's make things even more complicated by adding in over-time pay (1.5x the regular rate)! This is actually going to be pretty simple
