Dismantling the Simplex algorithm: recognizing tight constraints
Admittedly, the title is a little dramatic. What I’m introducing in this series on the Simplex algorithm is essentially a bunch of shortcuts. I’ll be the first to say that I love the Simplex algorithm. Yes, I realize we have spreadsheet software, along with all kinds of helpful AI to tell us how to use it. I’m pretty sure that there’s still at least one human out there writing code for that kind of software. Maybe my series of articles on the Simplex algorithm will only be of interest to that person. To me, these articles are worth writing because I find the Simplex algorithm fascinating and I like to experiment with it endlessly.
I’ll start off by picking the algorithm apart, but don’t worry I promise to put it back together. More specifically, I’ll explore linear programming (with three variables) and its use to solve maximization problems with constraints in a <= form. This might be a small set of problems within the broad topic of linear programming, but hey you gotta start somewhere! Because this is generally a very big topic, I won’t spend much time on each step of the algorithm. I highly recommend learning the algorithm itself (check out my Further Reading section for more references).
I know that I’ve been singing the praises of The Matrix, and admonishing you against skipping steps. When it comes to the Simplex algorithm, things get complicated pretty quickly. My goal in writing these articles is to show you cases where pivoting your way through a matrix can be avoided. In my first article (what you’re currently reading) I’ll look at scenarios with very tight constraints, or very limited resources. In these situations, constraints are so tight that an optimal solution can be obtained without using the Simplex algorithm. In fact, you may not even need a matrix. Without further ado, lets dive right into an example.
I’ll start with a building contractor example because it’s relatively easy to picture. (One more caveat: I’m definitely in favour of Land Back initiatives, but I’ve no idea how to deal with gentrification and urban sprawl. Maybe that can be the focus of another article some day.) Imagine a contractor whose specialty is building residential units. This builder has a certain amount of land, capital, and labour resources. This person knows that a particular amount of profit can be made per unit on 3 types of housing: condos, townhouses, and detached houses. Given that the constraints for this builder’s resources happen to fall into three tidy (linear) equations, one is tempted to throw everything into a matrix and start pivoting. Before going that far, it’s worth taking some time to consider the feasibility of your constraints.
How do you know when constraints are especially tight?
If you look at the sum total for a constraint and discover that at least one variable MUST be zeroed out (i.e., must be set to zero) in order to meet it, then you know you’re dealing with a tight constraint. I’ll show you what I mean.
We’ll start by assigning variables.
P = $20000x1 + $18000x2 + $24000x3
I’ll be honest, I know very little about real estate development so forgive me if these numbers seem off. Even if the profit for each type of housing is off, the objective function still helps us to maximize the total amount made.
Now for some tight constraints. Our builder happens to be low on resources at the moment, working with a total of 10 acres, $80000 in capital, and 4000 labour hours. Each residence type has the following requirements:
$60000x1 + $60000x2 + $80000x3 <= $80000 in capital
4000x1 + 3000x2 + 4000x3 <= 4000 labour hours
Can you spot the constraints that are especially tight?
Right away, we can see that the second and third constraints prevent one of every house type being built. In order to meet these constraints, at least two of our variables MUST be zeroed out. What happens if we go ahead and try the Simplex algorithm out on these numbers anyway? The first pivot column occurs where we find the largest coefficient in the objective function. In this case it’s $24000, the coefficient of x3. Then we take each constraint’s sum total and divide it by the respective x3 coefficient:
10/2 = 5
80000/80000 = 1
4000/4000 = 1
When we compare these resulting quotients, we can see that both constraint two and constraint three have the same quotient value which is 1. If we were going to pivot, we’d choose the row (or constraint) under column x3 that results in a minimum quotient to begin pivoting on. In this case, one option leads us to an optimal solution, the other gives us an incorrect answer. If we take a step back, and reconsider the problem from a practical perspective we might find the optimal solution is staring us right in the face.
The largest profit per unit is associated with x3. If we assign a value of 1 to this variable, we see that all constraints are used up and there’s no way to further increase profit.
2(1) <= 10
$80000(1) = $80000
4000(1) = 4000
Therefore the optimal solution is P = $24000(1).
What happens if we loosen the constraints a little?
Our building contractor realizes that these constraints don’t give us much to work with. Instead, we’re provided with revised constraints for capital and labour.
3000x1 + 1000x2 + 4000x3 <= 4000 labour hours
Because this is an imaginary example, we won’t question what kind of condo and townhouse models require 3000 and 1000 labour hours respectively. We’ll just ask, do these changes result in a profit increase?
First of all, lets do a quick tight-constraint check:
$60000(1) + $60000(1) + $80000(0) <= $120000 in capital
3000(1) + 1000(1) + 4000(0) <= 4000
Now it’s possible to meet both of these constraints by only zeroing-out one variable. When we set the other two variables to 1, we can see that both of these constraints are used up which means there’s no way to further increase profit.
Returning to the objective function, we find that setting these two variables to 1 gives us a total profit of:
P = $20000(1) + $18000(1) + $24000(0) = $38000.
As it turns out, these revised constraints result in a profit increase. (In other words, an increased investment of $40000 in capital, 120000/80000=1.5, results in a 1.58 increase in profit, 38000/24000=1.58.)
What happens if our builder informs us that there’s only 2 acres on which to build? The first constraint is now:
Assuming all else remains the same, do we need to pivot in order to find an optimal solution? No! Again, we see that all constraints can still be met by assigning the value 1 to x1 and x2. This assignment uses up all constraint sum totals, therefore no further increase in profit can be obtained.
In fact, if we were to use the Simplex algorithm with this change in our first constraint we’d again be faced with a choice very similar to our initial tight constraints. When choosing a row on which to pivot, we’d be provided with the same minimum quotient value for two rows. One choice leads to an optimal solution, the other leads to an incorrect answer. Because this problem occurs more frequently when dealing with tight constraints, it’s usually better to avoid using the Simplex algorithm for these cases.
CONCLUSION
This first article is just about recognizing tight constraints (i.e., one or more variables MUST be set to zero to meet a constraint). In these cases it’s often easier to avoid the Simplex algorithm completely. What can you do instead? I’ll need a whole other article to explain that ;)