TY - JOUR
SN - 0171-6468
AU - Albers, Sönke
T1 - Implicit enumeration algorithms for the set-partitioning problem
T2 - OR-Spektrum
SP - 23
EP - 32
IS - 1
VL - 2
PY - 1980
L1 - http://dx.doi.org/10.1007/BF01720155
AB - A new column enumeration algorithm for solving the Set-Partitioning Problem is presented. It is not based on the staircase form of the coefficient matrix. Rather, it uses a preordering of the variables with respect to their cost of covering one row that is a supposition of a new strong lower bound concept. The enumeration process itself is organized similar to a general branch-and-bound concept. The performance of the algorithm is evaluated on the basis of a systematic comparison with different variants of the wellknown algorithms by Pierce and Garfinkel-Nemhauser. The computational experiences indicate that the new algorithm is superior for problems with moderatly dense coefficient matrices.
TS - EndNote Tagged Import Format
DO - 10.1007/BF01720155
ER -