Integer Linear Programming
An optimization problem consists of an objective function to be maximized/minimized and a series of constraints on the solution. As we will discuss in future posts, perhaps contrary to intuition, it’s in fact harder to solve problems where both the objective and constraints are linear since small changes in the inputs can lead to significant, discrete changes in the answer. However, the famous simplex algorithm can be employed to tame most of these problems. It is, in fact, “unreasonably” successful in doing so: there are theoretical instances where the simplex method might take an inordinate amount of time to work, but these situations don’t seem to arise in practice very often.
In this post, we introduce a new twist on the optimization problem, one which will take us from classic optimization to the new generation of linear programming problems and solution techniques: the requirement that the values of the variables be integers, and the field is known in general as Integer Linear Programming (ILP). (If some variables can be continuous and others integers, we use the abbreviation MIP, for Mixed Integer Programming.)
It’s not hard to think of problems where fractional solutions make no sense. Consider the creation of a schedule for a Major League Baseball season — you can’t have a team play another team 6.2 times during the season. Or the crucial problem of where to seat guests for a wedding reception — you can’t have 7.8 guests at one table. Or facility location — each new building has to actually exist at one place, not be fractionally spread out across multiple locations.
Graphically, the problem is illustrated in the figure below. We can solve the linear programming problem as before and get the overall optimal solution. But now we add the requirement that the solution falls on a grid point inside the feasible region. Thus to solve the problem we will have to explore the interior of the convex hull created by the problem’s constraints, terra incognita for us up to this point.
Conceptually, it’s not hard to see how one could arrive at the solution; take the level set of the objective function, start at the global optimum, and then slide it back towards the origin. The first time this hits a grid point (all variables have integer values) that’s the solution.
Unfortunately, although this isn’t so hard to visualize in 2 dimensions, it’s not at all obvious how to figure this out when there are hundreds, thousands, or more variables in the problem. It’s an NP-complete problem, and so head-on attempts to solve it will, in general, be fruitless. And there’s no one-size-fits-all approach like the simplex algorithm that we can use to tackle these problems, so we will need a toolbox of methods that can be applied under various circumstances.
The first and most important of these tools is relaxation, the subject of the next post.
