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

opti100
9317
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.

link

answered 26 Feb '16, 19:31

Totalunimodular's gravatar image

Totalunimodular
412
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.

link

answered 29 Feb '16, 22:48

Matthew%20Saltzman's gravatar image

Matthew Salt... ♦
4.7k310
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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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

Tags:

×190

Asked: 26 Feb '16, 18:34

Seen: 604 times

Last updated: 29 Feb '16, 22:48

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