I was tasked with constructing an integer programming formulation for an NP-hard problem, and then with specifying its LP relaxation and the resulting approximation factor.

The problem is that, while my integer programming formulation is correct and clever (I like to think), it seams that its relaxation is completely useless. In fact, the LP relaxation seams like it would always lead to the worst possible solution to the original problem.

Is this possible? Is there some known way of deriving a proof that an LP relaxation of an IP problem can only be so good, some way of telling you when to quit looking?


Yes, some IP formulations are less useful than others. The technique used to show that an LP relaxation can only be so good is showing integrality gaps. For a minimization problem, an integrality gap of $k$ in an instance in which the optimal integer solution has value $V$ but the LP has a solution of value at most $V/k$. This shows that any rounding mechanism cannot guarantee an approximation ratio better than $k$.

As a simple example, consider the relaxation of the vertex cover IP $x_i + x_j \geq 1$ for every edge $(i,j) \in E$ (the variables are $x_i$ for every vertex $i$, and they are constrained to lie in $[0,1]$). A triangle has minimum vertex cover 2, but the LP has a solution with value only 3/2 (namely, all vertices get the value 1/2). This is an integrality gap of 4/3. There are more complicated integrality gaps of $2-\epsilon$ for every $\epsilon > 0$.

| cite | improve this answer | |
  • $\begingroup$ In my case, it's a maximization problem and it seams impossible to prove, for any rounding method, that the LP relaxation guarantees anything better than 0 times the optimal IP solution. On a side note, my solution seams to use an order of magnitude less variables and constraints than the solutions I find in the textbooks. However, the textbook solution is simpler and has a relaxation that leads to a 2-factor approximation. In practice, would my solution likely still be slower to solve by an integer programming solver? $\endgroup$ – MVTC Nov 15 '15 at 11:58
  • 1
    $\begingroup$ An integrality gap doesn't depend on any rounding technique. It gives a limitation on all rounding techniques. While I described it for minimization problems, maximization problems are handled analogously, with the small necessary changes. $\endgroup$ – Yuval Filmus Nov 15 '15 at 12:02
  • $\begingroup$ Regarding solvability by IP solvers, this is an empirical question. $\endgroup$ – Yuval Filmus Nov 15 '15 at 12:02
  • $\begingroup$ You can have different relaxations of the IP formulation though right, and each can have a different integrality gap. Is there some way to prove bounds on what the best integrality gap is for any relaxation of an IP formulation? $\endgroup$ – MVTC Nov 16 '15 at 10:31
  • $\begingroup$ @MVTC I think there is usually an exponential IP without any integrality gap. $\endgroup$ – Yuval Filmus Nov 16 '15 at 10:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.