Experiments in integer programming

Abstract

A hybrid algorithm to solve large scale zero-one integer programming problems has been developed. The algorithm combines branch-and-bound, enumeration and cutting plane techniques. Mixed-integer cuts are generated in the initial phase of the algorithm and added to the L.P. Benders cuts are derived and used implicitly but, except for the cut from the initial LP, are not stored. The algorithm has been implemented on an experimental basis in MPSX/370 using its Extended Control Language and Algorithmic Tools. A computational study based on five well-known difficult test problems and on three practical problems with up to 2000 zer-one variables shows that the hybrid code compares favorably with MIP/370 and with results published for other algorithms. © 1980.