SOLVING LARGE-SCALE ZERO-ONE LINEAR-PROGRAMMING PROBLEMS

A report is presented 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 the computational procedures do not exploit directly. By today's standards, the methodology produced impressive computational results, particularly on sparse problems having no apparent special structure. The computational results on problems with up to 2750 variables strongly confirm the 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.