A network relaxation based enumeration algorithm for set partitioning

Hidden network structure in the element-set incidence constraint matrix of a set partitioning problem can be identified by using procedures for testing when a binary matrix is transformable to a network. The set partitioning problem is thus represented as a network with side constraints. This paper reports the development of a new efficient solution procedure for the set partitioning problem facilitated by the new formulation and makes use of Lagrangean duality, modified subgradients, efficient reoptimization and enumeration tree reduction.