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. Thanks!
asked
AnORStudent |

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