A network relaxation based enumeration algorithm for set partitioning (Q1123128)

The authors propose a method for the solution of a set partitioning problem which is based on the fact that the partitioning problem can be solved by a linear programming method if its constraints matrix is totally unimodular. In the general case the method tries to extract a network matrix from the constraints matrix and to reduce the original problem to a network problem with side constraints. The authors solve the last problem by using an enumeration method. Several computational results are included in the paper.