Solving Large-Scale Zero-One Linear Programming Problems

Harlan Crowder, Ellis L. Johnson and Manfred Padberg
Additional contact information
Harlan Crowder: IBM Thomas J. Watson Research Center, Yorktown Heights, New York
Ellis L. Johnson: IBM Thomas J. Watson Research Center, Yorktown Heights, New York
Manfred Padberg: New York University, New York, New York

Operations Research, 1983, vol. 31, issue 5, 803-834

Abstract: In this paper we report on the solution to optimality of 10 large-scale zero-one linear programming problems. All problem data come from real-world industrial applications and are characterized by sparse constraint matrices with rational data. About half of the sample problems have no apparent special structure; the remainder show structural characteristics that our computational procedures do not exploit directly. By today's standards, our methodology produced impressive computational results, particularly on sparse problems having no apparent special structure. The computational results on problems with up to 2,750 variables strongly confirm our hypothesis that a combination of problem preprocessing, cutting planes, and clever branch-and-bound techniques permit the optimization of sparse large-scale zero-one linear programming problems, even those with no apparent special structure, in reasonable computation times. Our results indicate that cutting-planes related to the facets of the underlying polytope are an indispensable tool for the exact solution of this class of problem. To arrive at these conclusions, we designed an experimental computer system PIPX that uses the IBM linear programming system MPSX/370 and the IBM integer programming system MIP/370 as building blocks. The entire system is automatic and requires no manual intervention.

Keywords: 625 problem preprocessing; brand and bound; cutting planes; 628 facets of zero-one linear programs (search for similar items in EconPapers)
Date: 1983
References: Add references at CitEc
Citations: View citations in EconPapers (67)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.31.5.803 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:31:y:1983:i:5:p:803-834

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().