A new modeling and solution approach for the set-partitioning problem

Lewis, Mark, Kochenberger, Gary, and Alidaee, Bahram
Computers & Operations Research Vol. 35, Issue 3, p. 807-813

The set-partitioning problem (SPP) is widely known for both its application potential and its computational challenge. This NP-hard problem is known to pose considerable difficulty for classical solution methods such as those based on LP technologies. In recent years, the unconstrained binary quadratic program has proven to perform well as a unified modeling and solution framework for a variety of IP problems. In this paper we illustrate how this unified framework can be applied to SPP. Computational experience is presented, illustrating the attractiveness of the approach.