Article ID: | iaor20003200 |
Country: | United States |
Volume: | 1 |
Issue: | 4 |
Start Page Number: | 247 |
End Page Number: | 259 |
Publication Date: | Oct 1995 |
Journal: | Journal of Heuristics |
Authors: | Savelsbergh M.W.P., Nemhauser George L., Atamtrk A. |
Keywords: | heuristics, programming: linear |
Given a finite ground set, a set of subsets, and costs on the subsets, the set partitioning problem is to find a minimum cost partition of the ground set. Many combinatorial optimization problems can be formulated as set partitioning problems. We present an approximation algorithm that produces high-quality solutions in an acceptable amount of computation time. The algorithm is iterative and combines problem size-reduction techniques, such as logical implications derived from feasibility and optimality conditions and reduced cost fixing, with a primal heuristic based on cost perturbations embedded in a Lagrangian dual framework, and cutting planes. Computational experiments illustrate the effectiveness of the approximation algorithm.