A Combined Lagrangian, Linear Programming and Implication Heuristic for Large-Scale Set Partitioning Problems

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. Computational experiments illustrate the effectiveness of the approximation algorithm. Keywords: set partitioning, preprocessing, linear programming, Lagrangian dual September 1995 1 Introduction 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. Let A be an..