FN ISI Export Format
VR 1.0
PT J
TI Implicit enumeration algorithms for the set-partitioning problem
AF Albers, Sönke
AU Albers, S
SO OR-Spektrum
SN 0171-6468
VL 2
BP 23
EP 32
PY 1980
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.
DI 10.1007/BF01720155
ER