In my last post on game theory, I said that you could find an optimal probabilistic grand strategy for any two-player, simultaneous move, zero-sum game. It's done through something called linear programming. But linear programming is useful for a whole lot more than just game theory.

Linear programming is a general technique for solving a huge family of optimization problems. It's incredibly useful for scheduling, resource allocation, economic planning, financial portfolio management, and a ton of of other, similar things.

The basic idea of it is that you have a linear function, called an objective function, which describes what you'd like to maximize. Then you have a collection of inequalities, describing the constraints of the values in the objective function. The solution to the problem is a set of assignments to the variables in the objective function that provide a maximum.

For example, imagine that you run a widget factory, which can produce a maximum of W widgets per day. You can produce two different kinds of widgets - either widget 1, or widget 2. Widget one takes s₁ grams of iron to produce; widget 2 needs s₂ grams of iron. You can sell a widget 1 for a profit p₁ dollars, and a widget 2 for a profit of p₂ dollars. You've got G grams of iron available for producing widgets. In order to maximize your profit, how many widgets of each type should you produce with the iron you have available to you?

You can reduce this to the following:

1. You want to maximize the objective function p₁x₁ + p₂x₂, where x₁ is the number of type 1 widgets you'll produce, and x₂ is the number of type 2 widgets.
2. x₁ + x₂ ≤ W. (You can't produce more than W widgets.)
3. s₁x₁ + s₂x₂ ≤ G. (This is the constraint imposed by the amount of iron you have available to produce widgets.)
4. x₁ ≥ 0, x₂ ≥ 0. (You can't produce a negative number of either type of widgets.)

The fourth one is easy to overlook, but it's really important. One of the tricky things about linear programming is that you need to be sure that you really include all of the constraints. You can very easily get non-sensical results if you miss a constraint. For example, if we left that constraint out of this problem, and the profit on a type 2 widget was significantly higher than the profit on a type 1 widget, then you might wind up producing a negative number of type 1 widgets, in order to allow you to produce more than W widgets per day.

Once you've got all of the constraints laid out, you can convert the problem to a matrix form, which is what we'll use for the solution. Basically, for each constraint equation where you've got both x₁ and x₂, you add a row to a coefficient matrix containing the coefficients, and a row to the result matrix containing the right-hand side of the inequality. So, for example, you'd convert the inequality "s₁x₁ + s₂x₂ ≤ G" to a row [s₁,s₂] in the coefficient matrix, and "G" as a row in the result matrix. This rendering of the inequalities is show below.

Maximize:

where

Once you've got the constraints worked out, you need to do something called adding slack. The idea is that you want to convert the inequalities to equalities. The way to do that is by adding variables. For example, given the inequality x₁ + x₂≤W, you can convert that to an equality by adding a variable representing W-(x₁+x₂): x₁+x₂+x_slack=W, where x_slack≥0.

So we take the constraint equations, and add slack variables to all of them, which gives us the following:

1. Maximize: p₁x₁ + p₂x₂
2. x₁ + x₂ + x₃ = W.
3. s₁x₁ + s₂x₂ + x₄ = G.
4. x₁ ≥ 0, x₂ ≥ 0.

We can re-render this into matrix form - but the next matrix needs to includes rows and columns for the slack variables.

Now, we need to work the real solution into the matrix. The way that we do that is by taking the solution - the maximum of the objective function - and naming it "Z", and adding the new objective function equation into the matrix. In our example, since we're trying to maximize the objective "p₁x₁ + p₂x₂", we represent that with an equation "Z-p₁x₁-p₂x₂=0". So the final matrix, called the augmented form matrix of our linear programming problem is:

Once you've got the augmented form, there are a variety of techniques that you can use to get a solution. The intuition behind it is fairly simple: the set of inequalities, interpreted geometrically, form a convex polyhedron. The maximum will be at one of the vertices of the polyhedron.

The simplest solution strategy is called the simplex algorithm. In the simplex algorithm, you basically start by finding an arbitrary vertex of the polyhedron. You then look to see if either of the edges incident to that point slope upwards. If they do, you trace the edge upward to the next vertex. And then you look to see if the other edge from that vertex slopes upwards - and so on, until you reach a vertex where you can't follow an edge to a higher point.

In general, solving a linear programming problem via simplex is pretty fast - but it's not necessarily so. The worst case time of it is exponential. But in real linear programming problems, the exponential case basically doesn't come up.

(It's like a wide range of problems. There are a lot of problems that are, in theory, incredibly difficult - but because the difficult cases are very rare and rather contrived, they're actually very easy to solve. Two examples of this that I find particularly interesting are both NP complete. Type checking in Haskell is one of them: in fact, the general type inference in Haskell is worse that NP complete: the type validation is NP-complete; type inference is NP-hard. But on real code, it's effectively approximately linear. The other one is a logic problem called 3-SAT. I once attended a great talk by a guy named Daniel Jackson, talking about a formal specification language he'd designed called Alloy. Alloy reduces its specification checking to 3-SAT. Dan explained this saying: "The bad news is, analyzing Alloy specifications is 3-SAT, so it's exponential and NP-complete. But the good news is that analyzing Alloy specifications is 3-SAT, so we can solve it really quickly.")

This is getting long, so I think I'll stop here for today. Next post, I'll show an implementation of the simplex algorithm, and maybe talk a little bit about the basic idea behind the non-exponential algorithms. After that, we'll get back to game theory, and I'll show how you can construct a linear programming problem out of a game.