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?