Solving Large-Scale Zero-One Linear Programming Problems

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.