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

TLDR

Branch‑and‑cut is summarized, including flowcharts, as a standard approach for general zero‑one problems. The study presents techniques to automatically improve the LP representation of general zero‑one linear programs. The authors detect redundant rows and infeasibilities, reduce coefficients with the Euclidean algorithm, perform optimality fixing and variable elimination, and extend these methods to special‑ordered‑set constraints. Numerical experiments on eleven large‑scale real‑world zero‑one linear‑programming problems show the preprocessing improves branch‑and‑cut performance. An illustrative example appears in the Appendix; the article was published in INFORMS Journal on Computing (ISSN 1091‑9856, formerly ORSA Journal on Computing, ISSN 0899‑1499).

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.