Apologies if this question is basic.

The case we're all taught in class for the LP relaxation being equal to the linear program is a totally unimodular coefficient matrix. What are other conditions, necessary and/or sufficient?

I don't have a specific use for this right now, but I'm curious because the Wikipedia page for LP relaxation

http://en.wikipedia.org/wiki/Linear_programming_relaxation

seems to imply there are other conditions but I never see any others mentioned.

Thanks!

asked 10 Jul '10, 01:33

AnORStudent's gravatar image

AnORStudent
323314
accept rate: 0%


Total unimodularity leads to integral solutions for all right hand sides. But if you limit the right hand side, you can get other integral polyhedron (or LP=IP for short). Balanced matrices for set packing is one example. Chapters 21 and 22 of Schrijver's "Theory of linear and integer programming" offers some further results.

link

answered 10 Jul '10, 02:08

Michael%20Trick's gravatar image

Michael Trick ♦♦
4.1k51533
accept rate: 20%

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: 10 Jul '10, 01:33

Seen: 1,168 times

Last updated: 10 Jul '10, 02:08

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