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's gravatar image

accept rate: 0%

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's gravatar image

accept rate: 0%

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%20Saltzman's gravatar image

Matthew Salt... ♦
accept rate: 17%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "Title")
  • 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



Asked: 26 Feb '16, 18:34

Seen: 722 times

Last updated: 29 Feb '16, 22:48

OR-Exchange! Your site for questions, answers, and announcements about operations research.