Exact Implicit Enumeration Method for Solving the Set Partitioning Problem

The partitioning problem may be stated as follows: Minimize ∑j=1ncjxjsubject to ∑j=1naijxj= 1, i=1, · · ·, m, where aijand xjare binary numbers. The proposed method consists in solving a new problem equivalent to the original one, the solution of this new problem being obtained by implicit enumeration. Computational experience indicates that this approach yields good results; for example, problems involving several hundred variables were solved in a few seconds.