2.4. The Computational Complexity of LP and ILP

Now that we know what linear programs and integer linear programs are, and we got a glimpse of how to model optimization problems as LPs or ILPs, the next question is how we find optimal solutions for LPs and ILPs.

Linear Programming

In Chapter 3, we discuss the Simplex Algorithm as a classical algorithm for solving LPs. The Simplex Algorithm is the most popular algorithm for solving linear programs in practice, and it is also among the fastest algorithms in practice to solve many LPs. For some pathological inputs, however, the Simplex Algorithm may take exponential time and thus does not find a solution efficiently. Remarkably, any such pathological input has an almost identical input "nearby" that takes the Simplex Algorithm polynomial time to solve (Spielman and Teng, 2004). Thus, we have to try really, really hard if we want to make the Simplex Algorithm take exponential time.

Still, in theory, the Simplex Algorithm is not a polynomial-time algorithm. The Ellipsoid Algorithm and Karmarkar's Algorithm, not discussed here, can solve every linear program in polynomial time. More importantly, the Ellipsoid Algorithm can do that even for LPs with an exponential number of constraints, provided these constraints are represented appropriately: The Ellipsoid Algorithm relies on a "separation oracle" to drive its search for an optimal solution. Even if the LP technically has an exponential number of constraints, it may be possible to implement a separation oracle for the LP that runs in polynomial time and space. If that's the case, then the Ellipsoid Algorithm solves the LP in polynomial time. In practice, the Ellipsoid Algorithm suffers from numerical instability and is much slower than both the Simplex Algorithm and Karmarkar's Algorithm.

Even though we do not discuss the Ellipsoid Algorithm or Karmarkar's algorithm in these notes, the main take-away from this short subsection is that

Theorem 2.6: Any linear program can be solved in polynomial time in its size.

Integer Linear Programming

So we can solve linear programs in polynomial time. What about integer linear programs? In the remainder of this section, we prove that solving integer linear programs is NP-hard, even if they have only a polynomial number of constraints.

Recall the basic strategy for proving that a problem \(\Pi\) is NP-hard. It suffices to provide a polynomial-time reduction from an NP-hard problem \(\Pi'\) to \(\Pi\). Specifically, we need to provide a polynomial-time algorithm \(\mathcal{A}\) that takes any instance \(I'\) of \(\Pi'\) and computes from it an instance \(I\) of \(\Pi\) such that \(I\) is a yes-instance of \(\Pi\) if and only if \(I'\) is a yes-instance of \(\Pi'\). If you have not seen any NP-hardness proofs yet or you need a refresher on how they work, the appendix provides a brief introduction to the topic.

Here, we choose \(\Pi\) to be ILP and \(\Pi'\) to be the satisfiability problem (SAT). A SAT instance is a Boolean formula in CNF over some set of variables \(x_1, \ldots, x_n\):

\[\begin{aligned} F &= C_1 \wedge \cdots \wedge C_m\\ C_i &= \lambda_{i1} \vee \cdots \vee \lambda_{ik_i} && \forall 1 \le i \le m\\ \lambda_{ij} &\in \{ x_1, \ldots, x_n, \bar x_1, \ldots, \bar x_n \} && \forall 1 \le i \le m, 1 \le j \le k_i. \end{aligned}\]

\(\bar x_i\) denotes the negation of \(x_i\).

We translate \(F\) into an ILP over variables \(x_1, \ldots, x_n \in \{0,1\}\). Each literal \(\lambda_{ij}\) is translated into a linear function \(\phi_{ij}(x_1, \ldots, x_n)\) defined as

\[\phi_{ij}(x_1, \ldots, x_n) = \begin{cases} x_k & \text{if } \lambda_{ij} = x_k\\ 1 - x_k & \text{if } \lambda_{ij} = \bar x_k \end{cases}.\]

Each clause \(C_i\) is translated into the constraint

\[\Phi_i(x_1, \ldots, x_n) \ge 1,\]

where

\[\Phi_i(x_1, \ldots, x_n) = \sum_{j=1}^{k_i} \phi_{ij}(x_1, \ldots, x_n).\]

It turns out that even deciding whether this ILP has a feasible solution is NP-hard, so we can choose any objective function, such as \(f(x_1, \ldots, x_n) = 0\), to complete the definition of the ILP.

To prove that deciding whether this ILP has a feasible solution is NP-hard, we prove that \(F\) is satisfiable if and only if the ILP has a feasible solution:

First assume that \(F\) is satisfiable. Then there exists an assignment \(\hat x = \bigl(\hat x_1, \ldots, \hat x_n\bigr)\) of truth values to the variables \(x_1, \ldots, x_n\) in \(F\) such that every clause \(C_i\) contains a true literal \(\lambda_{ij}\). For this literal, \(\phi_{ij}\bigl(\hat x_1, \ldots, \hat x_n\bigr) = 1\). Thus, since \(\phi_{ij'}\bigl(\hat x_1, \ldots, \hat x_n\bigr) \ge 0\) for all \(1 \le j' \le k_i\), \(\Phi_i\bigl(\hat x_1, \ldots, \hat x_n\bigr) = \sum_{j'=1}^{k_i} \phi_{ij'}\bigl(\hat x_1, \ldots, \hat x_n\bigr) \ge 1\), that is, \(\hat x\) satisfies the constraint corresponding to \(C_i\) in the ILP. Since \(\hat x\) satisfies every clause of \(F\), this shows that it satisfies every constraint of the ILP, so \(\hat x\) is a feasible solution of the ILP.

Now assume that the ILP is feasible. Then there exists a feasible solution \(\hat x = \bigl(\hat x_1, \ldots, \hat x_n\bigr)\) of the ILP. Since \(\hat x_i \in \{0, 1\}\) for all \(1 \le i \le n\), we can interpret this solution as an assignment of truth values to the variables \(x_1, \ldots, x_n\) in \(F\). Since \(\hat x\) is a feasible solution of the ILP, we have \(\Phi_i\bigl(\hat x_1, \ldots, \hat x_n\bigr) = \sum_{j'=1}^{k_i} \phi_{ij'}\bigl(\hat x_1, \ldots, \hat x_n\bigr) \ge 1\) for every clause \(C_i\). Thus, \(\phi_{ij}\bigl(\hat x_1, \ldots, \hat x_n\bigr) = 1\) for at least one literal \(\lambda_{ij} \in C_i\), that is, \(\lambda_{ij}\) is made true by the solution \(\hat x = \bigl(\hat x_1, \ldots, \hat x_n\bigr)\) and, thus, \(C_i\) is satisfied by \(\hat x\). Since \(\hat x\) satisfies every constraint in the ILP, it also satisfies every clause \(C_i\) in \(F\), that is, it is a satisfying truth assignment of \(F\).

We have shown that we can, in polynomial time, convert any Boolean formula \(F\) into an ILP that is feasible if and only if \(F\) is satisfiable. This conversion is a polynomial-time reduction from SAT to ILP. Since SAT is NP-hard, this proves that

Theorem 2.7: Integer linear programming is NP-hard.