REFORMULATION OF THE SET PARTITIONING PROBLEM AS A PURE NETWORK WITH SPECIAL ORDER SET CONSTRAINTS

In this paper, the set partitioning problem is reformulated as a netwo rk flow problem with special order sets. The reformulation is based on identifying network structure that is hidden in the element-set incid ence matrix. The special order sets and the revealed network in the re formulation together define an effective structure for solution by enu meration. The resulting enumeration procedure for the solution of the set partitioning problem is computationally advantageous since it uses a pure network relaxation that is solved using reoptimization, allows a large number of variables to be fixed in a subproblem, and is defin ed over a relatively small enumeration tree. Computational experience is included.