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


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


asked 10 Jul '10, 01:33

AnORStudent's gravatar image

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.


answered 10 Jul '10, 02:08

Michael%20Trick's gravatar image

Michael Trick ♦♦
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



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



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.