2.5. LP Relaxations

Given that we have polynomial-time algorithms for solving LPs but solving ILPs is NP-hard, an important question is whether we can use the machinery for solving LPs to obtain suboptimal but good solutions for ILPs. We will explore this question in the third part of this book. Here, we introduce an important tool for translating ILPs into related LPs: LP relaxation.

For every ILP, one can define a corresponding LP by simply dropping the requirement that the solution value of each variable be an integer: in the LP solution, variables are allowed to take on any real values as long as they satisfy the constraints in the LP.

The LP relaxation of an ILP is the same as the ILP, but the requirement that the variable values in a feasible solution be integers is dropped.

As an example, here is the LP relaxation of (2.9). It is identical to the ILP, except that the constraint \(x_e \in \{0, 1\}\) has been replaced with the constraint \(0 \le x_e \le 1\): \(x_e\) is no longer required to be integral:

\[\begin{gathered} \text{Minimize } \sum_{e \in E} w_e x_e\\ \begin{aligned} \text{s.t. } \sum_{e \in E} x_e &= n - 1\\ \sum_{e \in C} x_e &\le |C| - 1 && \forall \text{cycle $C$ in $G$}\\ 0 &\le x_e \le 1 && \forall e \in E. \end{aligned} \end{gathered}\tag{2.12}\]

In general, the LP relaxation of an ILP may have a much better optimal solution than the ILP itself, but it can never have a worse optimal solution:

Lemma 2.8: If \(\hat x\) is an optimal solution to a minimization ILP \(P\) and \(\tilde x\) is an optimal solution to its LP relaxation \(P'\), then \(f\bigl(\tilde x\bigr) \le f\bigl(\hat x\bigr)\), where \(f\) is the objective function shared by \(P\) and \(P'\).

Proof: Since \(\hat x\) is a feasible solution of \(P\), it is also a feasible solution of \(P'\). Since \(\tilde x\) is an optimal solution of \(P'\), this implies that \(f\bigl(\tilde x\bigr) \le f\bigl(\hat x\bigr)\). ▨

The ratio \(f\bigl(\hat x\bigr) \mathop{/} f\bigl(\tilde x\bigr)\) between the optimal objective function values of the ILP and its relaxation is called the integrality gap of the ILP.

In general, this gap can be arbitrarily large. However, for problems where the integrality gap is bounded, the LP relaxation can often be used to efficiently obtain an approximation of the optimal solution of the ILP, a fact that will be explored further when we discuss Chapter 13. Another useful property exploited by some approximation algorithms is half-integrality of the optimal solution of some LPs: In the optimal solution, every variable takes on a value that is a multiple of \(\frac{1}{2}\). Again, this will be explored further when discussing approximation algorithms.