Is it possible to write for a given MIP a LP with exponential many constraints, which are aquivalent? If yes, why is it not possible with the Ellipsoid method to solve it in poly time?
asked
opti100 |

If you can separate the constraints in polynomial time, you can -in theory- solve your problem via the ellipsoid method in polynomial time too. The issue here is that separating constraints often requires solving NP-Hard problems.
answered
Totalunimodular |

Even if you can create an "equivalent" LP (in the sense that the LP describes the convex hull of integer solutions), that LP has size exponetial in the size of the original input. So solving the LP in polynomial time is not the same as solving the original MIP in polynomial time. Some integer programs (e.g., the general matching problem) have known complete LP descriptions of the convex hull of integer solutions that are exponential in size but can be solved in polynomial time. Having such a description is often a sign that a polynomial algorithm is possible. As @Totalunimodular points out, NP-complete decision problems have NP-complete separation problems as well.
answered
Matthew Salt... ♦ |