Using Surrogate Constraints in a Lagrangian Relaxation Approach to Set-Covering Problems

DOI10.1057/JORS.1988.115zbMATH Open0643.90061OpenAlexW2088339996MaRDI QIDQ3786281FDOQ3786281

Authors: C. Gregory John, Gary A. Kochenberger 

Publication date: 1988

Published in: The Journal of the Operational Research Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1057/jors.1988.115

Recommendations

• A surrogate heuristic for set covering problems
• scientific article; zbMATH DE number 4121754
• Surrogate gradient algorithm for Lagrangian relaxation
• Simple Lagrangian heuristic for the set covering problem
• Lagrangean relaxation. (With comments and rejoinder).

zbMATH Keywords

Lagrange multipliersbranch-and-boundComputational resultsset-coveringLagrangian relaxationsadding a single surrogate constraintLagrangian subproblems

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Integer programming (90C10)

Cited In (8)

• A surrogate heuristic for set covering problems
• Searching for optimal integer solutions to set partitioning problems using column generation
• Lagrangean relaxation for a lower bound to a set partitioning problem with side constraints: Properties and algorithms
• Dual-based heuristics for a hierarchical covering location problem
• Surrogate constraint normalization for the set covering problem
• Zero duality gap in surrogate constraint optimization: a concise review of models
• Solving linear programming relaxations associated with Lagrangean relaxations by Fenchel cutting planes
• A relax-and-cut algorithm for the set partitioning problem

This page was built for publication: Using Surrogate Constraints in a Lagrangian Relaxation Approach to Set-Covering Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3786281)