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?



How good is the LP relaxation?
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](https://www.springer.com/cda/content/document/cda_downloaddocument/9780387295039-c2.pdf?SGWID=0-0-45-321337-p107891199)* (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.


