n South African Computer Journal - An improved column subtraction method : reviewed article
|Article Title||An improved column subtraction method : reviewed article|
|© Publisher:||South African Computer Society (SAICSIT)|
|Journal||South African Computer Journal|
|Author||J.K. Loots, T.H.C. Smith and G.L. Thompson|
|Publication Date||Jun 2006|
|Pages||110 - 114|
|Keyword(s)||Branch-and-bound, Set partitioning and Zero-one programming|
The column subtraction method (CSM) is a branch-and-bound method for solving set partitioning, covering and packing problems. We present an improved CSM for the set partitioning problem and computational experience for an implementation of the improved CSM. Our computational experience shows that it is at least an order of magnitude faster than the original version on larger more complex problems and compares favorably with the branch-and-cut algorithm in solving real life airline crew scheduling problems.
Article metrics loading...