A simple strategy for solving a class of 0-1 integer programming models (Q1090232)

A strategy is proposed for solving certain generalized set packing models. The strategy is based on using a recently developed heuristic coupled with the solution of the linear programming relaxation of the model. The strategy is programmed, and execution times required for it to obtain optimal solutions to randomly generated models are compared to those required for an implementation of the Gomory cutting plane algorithm. The Cray 1 computer was used for all computations. Computational experience thus gained indicates that the proposed strategy is superior to the Gomory algorithm, and that it seems to perform relatively better on models with relatively higher-density constraint coefficient matrices.