So, I’ve finally had some time to get back to the linear programming
followup. You might want to go back and look at the earlier post to remember what I was talking about.
The basic idea is that we’ve got a system we’d like to optimize. The constraints of the system are defined by a set of linear inequalities, and
we’ve got a linear expression that we’d like to maximize.
So, for example, we could have a factory which is capable of producing two
different kinds of widgets. The factory has a maximum capacity of what it can
produce of 300 widgets per day. It gets a supply of metal and plastic for
making widgets: 5000 kilograms of steel, and 100 kilograms of plastic. There
are two kinds of widgets. Type 1 widgets take 23 kg of steel, and 2kg of
plastic, and sell for $900 each. Type 2 widgets take 5kg of steel, and 2
kilograms of plastic, and sell for $700 each. The factories customers need a
minimum of 5 type 1 and 2 type 2 widgets per day. So, the question is, what’s the optimal way to run the factory? How many of each widget should it make?
Using the formulation we discussed last time, we can formulate this
as a linear programming problem as follows:
- Let x1 be the number of type one widgets we produce.
- Let x2 be the number of type two widgets we produce.
- Objective: maximize 900x1 + 700x2, where:
- x1 + x2 ≤ 300
- 23x1 + 5x2 ≤ 500
- 2x1 + 2x2 ≤ 50
- x1 ≥ 5, x2 ≥ 2
Now, how do we get the answer? As I discussed last time,
there’s a conceptually simple algorithm called simplex. The
idea of the simplex algorithm is to do a basic form of something called hill-climbing. The idea of hill-climbing is really simple. You’re looking for the highest possible point in something which is modeled as a surface. So you try to go uphill: each step, you look for the next step which will get you the furthest up.
In simplex, you know that the solution is a vertex of an N-dimensional polygon. So you find an initial vertex – it doesn’t matter which one. Then you look at the edges that are incident on that vertex – and you pick the one that looks like it’ll get you the farthest uphill. You keep doing that until you get to one where no edge will take you to a higher vertex – and you’re at the maximum.
In general, simplex is very fast. Typically, even if you have the bad luck to start at a minimum vertex, you’ll get to the maximum very quickly. But the worst case is pretty bad: you can create LP problems where you’ll wind up visiting every vertex. You can see why by imagining a cube. You can distort the cube so that if you start at the minimum vertex, and always climb the edge with the steepest slope, you’ll have to visit every single vertex. And there are O(2n) vertices in an N-dimensional polygon. As you increase dimensions, you can do the same distortion trick, to force the simplex algorithm to visit all of the vertices. (Or at least O(2N) vertices.) But those cases are very rare, and frankly very contrived. So
in general, you don’t worry about them.
There are other algorithms to solve linear programming problems. There’s a very fast one – fast even in the pathological worst cases – called the interior points method. But for the most part, simplex is the way people go.
If you really need to solve a linear programming problem, you
don’t generally write simplex yourself. Implementing simplex
correctly is a pain. It’s typical of complex numerical analysis problems –
it’s a miserable pain in the ass to implement. But, it’s also such a common
problem that there are a huge number of highly optimized solvers already
written; you just grab one off the shelf. (There’s a lesson in there;
never waste time doing work yourself if you know someone else has already done it.) So, for this post, I grabbed a copy
of maxima, an open-source symbolic algebra system, which
includes a very nice solver.
In the last post, I showed how you can formulate the problem as a matrix, which is the input for the simplex algorithm. But maxima, since it’s so good at symbolic work, doesn’t even require you to do that (although most simplex solvers do take the problem in matrix form). Here’s how I wrote the problem as a maxima script:
load("simplex")$ maximize_lp( 9*x1 + 7*x2, [x1 + x2 <= 300, 23*x1 + 5*x2 <= 500, 2*x1 + 2*x2 <= 50, x1 >= 5, x2 >= 2]), nonegative_lp=true;
When I feed that in to maxima, it converts it to the matrix form,
and then solves it. The answer is that the maximum profit is
about $21,667, which you can make by producing 4 1/6 type 1 widgets,
and 20 5/6 type 2 widgets.
Now, that’s very nice isn’t it? We can maximize the factory’s profit
by producing 4 1/6 type one widgets. How how we produce 1/6th of a widget?
The way we formulated the problem is great for working out probabilities
for optimal grand strategies for zero-sum games – probabilities can
be arbitrary real numbers. But for the problem that we’re talking about – optimizing profit by producing discrete entities, you need an additional
constraint: the values in the solution must be integers.
For integer solutions, the simplex method goes right out the window. It’s actually an entirely different problem: integer linear programming. The strategies and solutions for solving ILP programs are quite different. Integer linear programming is a much harder problem. Instead of the polynomial time
algorithms that work for general LP, ILP is NP-hard – that is, its decision
problem (asking “Is this the optimal solution?”) is NP-complete; actually computing the answer is even worse.
Anyway, next post, we’ll get back to game theory – how we can set
up a zero-sum game as a linear programming matrix in order to find the
optimal grand strategy.