Section 6.1 Integer Linear Programs
An integer linear program (ILP) is a problem in which the goal is to maximize a linear function of \(n\) variables subject to linear constraits, just as in the linear programs that we studied in Chapter 2, but with the added integrality constraint which says that all variables must be integers. For example, any problem of the following type is an ILP
\begin{align*}
\text{max } \amp \amp c^Tx\\
\text{subject to } \amp \amp Ax\leq b.\\
\amp \amp x\in \mathbb{Z}^n
\end{align*}
where \(A\) is an \(m\times n\) real matrix, \(b\) is a real vector of length \(m\) and \(c\) is a real vector of length \(n\text{.}\) While ILPs may seem like only a mild variation on LPs, the differences between them are actually quite substantial. While LPs can be solved in polynomial time, it is actually quite easy to show that solving ILPs is NP-hard. In fact, most of the NP-hard problems discussed in these notes are pretty easy to simulate using an ILP (see, e.g., Exercise 3).
One natural strategy when faced with an ILP instance, or any hard problem for that matter, is to come up with a problem that can be solved efficiently and whose solution provides information about your original problem. For an ILP, the most natural candidate for a simpler problem is the LP that one obtains by removing the integrality constraint, which we call the LP relaxation of the ILP. Of course, for any maximization ILP, the value of the LP relaxation provides an upper bound for the value of the ILP. Of course, if one is lucky and the LP is maximized by an integer vector, then the value of the ILP and LP relaxation coincide and we can go home satisfied after a job well done.
Of course, much of the time, expecting the LP relaxation to be maximized at an integer vector is a unrealistic. However, our focus in the rest of the chapter is on a special condition on the constraints of an ILP which imply that the LP relaxation approach always works. As we shall see, this will provide yet another approach to the maximum matching problem in bipartite graphs and the max-flow min-cut problem.
Before closing this section, we would like to mention one important result of Lenstra (that we won’t prove) on ILPs with a bounded number of variables because it is and interesting theorem and is worth being aware of.
In other words, if we have an ILP with a small number of variables, then we can check if it is feasible in time that is polynomial with respect to the size of the ILP. Of course, in such an algorithm, the dependence on \(n\) is can be poor, as any function of \(n\) is viewed as being a constant.
Here is a YouTube video related to this section:
