# Approximation MIP by LP with exponential many constraints

 2 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 26 Feb '16, 18:34 opti100 93●1●7 accept rate: 0%

 3 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 26 Feb '16, 19:31 Totalunimodular 41●2 accept rate: 0%
 2 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 29 Feb '16, 22:48 Matthew Salt... ♦ 4.7k●3●10 accept rate: 17%
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

×190