A combined Lagrangian, linear programming, and implication heuristic for large-scale set partitioning problems
✍ Scribed by A. Atamtürk; G. L. Nemhauser; M. W. P. Savelsbergh
- Publisher
- Springer US
- Year
- 1996
- Tongue
- English
- Weight
- 685 KB
- Volume
- 1
- Category
- Article
- ISSN
- 1381-1231
No coin nor oath required. For personal study only.
✦ Synopsis
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.