Improving LP-Representations of Zero-One Linear Programs for Branch-and-Cut

ORSA Journal on Computing · 1991 · Volume 3 · Issue 2

Abstract

We present various techniques for automatically improving the LP-representation of general zero-one linear programming problems. These include detection of redundant rows and blatant infeasibilities, coefficient reduction using the Euclidean algorithm, optimality fixing and variable elimination. Extensions to the case where special-ordered-set constraints are present are discussed as well. A summary of the branch-and-cut approach to general zero-one problems (including flowcharts) is given. We report numerical experiments to test the effect of such preprocessing within a branch-and-cut algorithm for eleven large-scale real-world zero-one linear-programming problems. An illustrative example is included in the Appendix. INFORMS Journal on Computing , ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Keywords

programming: integer: cutting plane/facet generation, relaxations, zero-one programming, preprocessing, automatic reformulation, branch-and-cut, scientific computation

Enable JavaScript for citation tools and additional paper interactions.