A combined Lagrangian, linear programming, and implication heuristic for large-scale set partitioning problems |
| |
Authors: | A Atamtürk G L Nemhauser M W P Savelsbergh |
| |
Institution: | (1) Georgia Institute of Technology, School of Industrial and Systems Engineering, 30332-0205 Atlanta, GA;(2) Georgia Institute of Technology, School of Industrial and Systems Engineering, 30332-0205 Atlanta, GA;(3) Georgia Institute of Technology, School of Industrial and Systems Engineering, 30332-0205 Atlanta, GA |
| |
Abstract: | 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. |
| |
Keywords: | set partitioning preprocessing linear programming Lagrangian dual |
本文献已被 SpringerLink 等数据库收录! |
|