# Conditions Where LP = IP?

 6 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 323●3●14 accept rate: 0%

 8 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 Trick ♦♦ 4.1k●4●15●33 accept rate: 20%
 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