# How good is the LP relaxation?

Consider the optimization problem \begin{align} \max_{x\in\mathbb{R}^n}~c^Tx~, \text{ s.t. } Ax=b,~x_i\in\{0,1\}~\forall i \end{align}where $$c,b\in\mathbb{R}_{+}^n$$ and $$A\in\mathbb{R}_{+}^{n\times n}$$. Thus $$x$$ is a boolean vector (entries can be $$0$$ or $$1$$). It is not hard to prove that this is a NP-hard problem. A typical approach to this problem is to relax the only non-linear constraint $$x\in\{0,1\}$$ and make it continuous so that $$0\leq x_i \leq 1$$. Is there any study on how good this approximation is?

• These types of problems are sometimes known as 'psuedo-boolean' optimization problems in that the function of interest is not boolean but the input is. – Josiah Park Dec 11 '18 at 8:49
• I guess the question is aimed at cases where total dual integrality and the likes do not apply, so the LP-relaxation solution is supposed to be different from the integer one, right? – Hannes Dec 11 '18 at 9:58

## 1 Answer

Yes. In chapter two, section three and four of Nemhauser and Wolsey's Integer and Combinatorial Optimization there are conditions detailed for various relaxations of the first problem to have solutions which are within $$\epsilon$$ of the original problem's solution.

For the problem you address specifically, Theorem 2.6 (on pg 17 in linked pdf) in Li and Sun's Nonlinear Integer Programming (although somewhat weak) gives the type of result it seems you are interested in (stated below). This result initially appeared in W. Cook, A. M. H. Gerards, A. Schrijver, and É. Tardos' paper Sensitivity theorems in integer linear programming published in 1986. Consider problems,

$$\hspace{15 mm} \min c^{T}x \\ (P)\hspace{15 mm} s.t.\ Ax\leq b \\ \hspace{15 mm} x\in \mathbb{Z}^{n}$$

and

$$\hspace{15 mm} \min c^{T}x \\ (P')\hspace{15 mm} s.t.\ Ax\leq b \\ \hspace{15 mm} x\in \mathbb{R}^{n}$$

where $$A$$ is an integer matrix, and $$c$$ and $$b$$ are real. Let $$\Delta(A)$$ be the maximum among the absolute values of all subdeterminants of $$A$$.

Theorem: Assume that the optimal solutions to ($$P$$) and ($$P'$$) both exist. Then for each optimal solution $$\overline{x}$$ to ($$P'$$), there exists an optimal solution $$z^{*}$$ to ($$P$$) such that $$\|\overline{x}-z^{*}\|_\infty \leq n \Delta(A).$$

Edit: The condition that $$A$$ is integer valued above should be noted. In the case $$A$$ is given as real valued then the problem can be scaled and rounded, but this will lead to much worse bounds.