A combined Lagrangian, linear programming, and implication heuristic for large-scale set partitioning problems

A combined Lagrangian, linear programming, and implication heuristic for large-scale set partitioning problems

0.00 Avg rating0 Votes
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: , ,
Keywords: heuristics, programming: linear
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.

Reviews

Required fields are marked *. Your email address will not be published.