A heuristic algorithm for the set covering problem

DOI10.1007/3-540-61310-2_6zbMath1415.90097OpenAlexW1489062326MaRDI QIDQ4645914

Matteo Fischetti, Paolo Toth, Alberto Caprara

Publication date: 11 January 2019

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-61310-2_6

zbMATH Keywords

Lagrangian relaxationsubgradient optimizationcrew scheduleLagrangian multiplier vectorlarge scale instance

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items

Thinning out Steiner trees: a node-based model for uniform edge costs, Perfect, ideal and balanced matrices, An adaptation of SH heuristic to the location set covering problem, A multi-depot pickup and delivery problem with a single hub and heterogeneous vehicles

Uses Software

• OR-Library

Cites Work

• Unnamed Item
• A Lagrangian-based heuristic for large-scale set covering problems
• A surrogate heuristic for set covering problems
• An algorithm for large scale 0-1 integer programming with application to airline crew scheduling
• Optimal Solution of Set Covering/Partitioning Problems Using Dual Heuristics
• Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study
• A Dynamic Subgradient-Based Branch-and-Bound Procedure for Set Covering
• The traveling-salesman problem and minimum spanning trees: Part II