A theoretical justification of the set covering greedy heuristic of Caprara et al.

DOI10.1016/J.DISOPT.2022.100700MaRDI QIDQ2172080zbMATH OpenOpenAlexFDO

Authors Torbjörn Larsson, Nils-Hassan Quttineh

Publication date 15 September 2022

Published in Discrete Optimization (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1016/j.disopt.2022.100700

zbMATH Keywords

global optimality conditionsgreedy heuristicsLagrangian relaxationset covering problem

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27) Optimality conditions and duality in mathematical programming (90C46)

Recommendations

• A heuristic algorithm for the set covering problem
• Pareto optimality and a class of set covering heuristics
• What is the best greedy-like heuristic for the weighted set covering problem?
• Absolute bounds on optimal cost for a class of set covering problems
• A probabilistic heuristic for a computationally difficult set covering problem

Cites work

• A dissection of the duality gap of set covering problems
• A Heuristic Method for the Set Covering Problem
• A Lagrangian-based heuristic for large-scale set covering problems
• An algorithm for set covering problem
• An integer programming column generation principle for heuristic search methods
• Computational experience with approximation algorithms for the set covering problem
• Dissecting the duality gap: the supporting hyperplane interpretation revisited
• Global Optimality Conditions for Discrete and Nonconvex Optimization—With Applications to Lagrangian Heuristics and Column Generation
• scientific article; zbMATH DE number 417962 (Why is no real title available?)
• scientific article; zbMATH DE number 439380 (Why is no real title available?)
• scientific article; zbMATH DE number 1818892 (Why is no real title available?)
• scientific article; zbMATH DE number 3791939 (Why is no real title available?)
• scientific article; zbMATH DE number 1312984 (Why is no real title available?)
• scientific article; zbMATH DE number 4121754 (Why is no real title available?)
• scientific article; zbMATH DE number 2121575 (Why is no real title available?)
• Simple Lagrangian heuristic for the set covering problem

Cited in

(3)

• Pareto optimality and a class of set covering heuristics
• What is the best greedy-like heuristic for the weighted set covering problem?
• Column generation extensions of set covering greedy heuristics

Describes a project that uses

Uses Software

• OR-Library

This page was built for publication: A theoretical justification of the set covering greedy heuristic of Caprara et al.

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