patternMinor
Are some Integer programming formulations completely useless for relaxation?
Viewed 0 times
relaxationformulationscompletelyareprogrammingsomeuselessforinteger
Problem
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?
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?
Solution
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$.
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$.
Context
StackExchange Computer Science Q#49511, answer score: 5
Revisions (0)
No revisions yet.