Improving LP-Representations of Zero-One Linear Programs for Branch-and-Cut
1991; Institute for Operations Research and the Management Sciences; Volume: 3; Issue: 2 Linguagem: Inglês
10.1287/ijoc.3.2.121
ISSN2326-3245
AutoresKarla Hoffman, Manfred Padberg,
Tópico(s)Multi-Criteria Decision Making
ResumoWe 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.
Referência(s)