A new approach for modeling and solving set packing problems

In recent years the unconstrained quadratic binary program has emerged as a unified modeling and solution framework for a variety of combinatorial optimization problems. Experience reported in the literature with several problem classes has demonstrated that this unified approach works surprisingly well in terms of solution quality and computational times, often rivaling and sometimes surpassing special purpose methods. In this paper we report on the application of this unified framework to set packing problems with a variety of coefficient distributions. Computational experience is reported illustrating the attractiveness of the approach. In particular, our results highlight both the effectiveness and robustness of our approach across a wide array of test problems. (C) 2007 Elsevier B.V. All rights reserved.