1
$\begingroup$

I am looking for an example where the optimal solution for the LP problem is equal to the optimal solution of the ILP problem, but the solutions are different.

All I managed to think of was the example of the knapsack problem, when the sum of all the weights were less than W (max weight). However, in this solution x=x', and I was looking for an example in which they are different.

I am a computer science undergraduate so if you have something I may understand it would be much appreciated.

Thank you

$\endgroup$
1
$\begingroup$

Consider any problem in which there are several different solutions, for example MAX-CLIQUE on a graph in which there are several cliques of maximum size. Any convex combination of optimal solutions in another optimal solution which isn't integral.

If the optimum value of the integer program is the same as its linear programming relaxation, then any optimal solution to the integer program is also an optimal solution of the linear program. The problem is that there could be other optimal solutions to the linear program, and an LP solver might find one of them instead of an integral optimal solution. It would be, however, inaccurate to say that the LP and ILP have the same value but not the same solution. Rather, all optimal solutions of the ILP are also optimal solutions of the LP. It's just that the LP has more optimal solutions.

$\endgroup$
  • $\begingroup$ Do you by any chance have a concrete example to give? $\endgroup$ – Lumon Jan 28 '18 at 14:47
  • 1
    $\begingroup$ You can try to come up with such an example on your own. $\endgroup$ – Yuval Filmus Jan 28 '18 at 22:09

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.