5
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

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$.

Improve this answer
$\endgroup$
5
  • $\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, 2015 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, 2015 at 12:02
  • $\begingroup$ Regarding solvability by IP solvers, this is an empirical question. $\endgroup$
    – Yuval Filmus
    Nov 15, 2015 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, 2015 at 10:31
  • $\begingroup$ @MVTC I think there is usually an exponential IP without any integrality gap. $\endgroup$
    – Yuval Filmus
    Nov 16, 2015 at 10:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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