Computational experience with general cutting planes for the set covering problem

DOI10.1016/j.orl.2008.09.009zbMath1154.90603OpenAlexW2006346540MaRDI QIDQ1002077

Pasquale Avella, Maurizio Boccia, Igor' Leonidovich Vasilyev

Publication date: 23 February 2009

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2008.09.009

zbMATH Keywords

cutting planesset coveringexact separation

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items (12)

Computational approaches for zero forcing and related problems ⋮ An implementation of exact knapsack separation ⋮ Optimizing word set coverage for multi-event summarization ⋮ Upgrading edges in the maximal covering location problem ⋮ Efficient heuristics for a partial set covering problem with mutually exclusive pairs of facilities ⋮ An improved configuration checking-based algorithm for the unicost set covering problem ⋮ A branch and cut heuristic for a runway scheduling problem ⋮ Experiments with LAGRASP heuristic for set \(k\)-covering ⋮ A mixed integer linear program and tabu search approach for the complementary edge covering problem ⋮ Strong bounds with cut and column generation for class-teacher timetabling ⋮ Computing the spark: mixed-integer programming for the (vector) matroid girth problem ⋮ A set covering approach for multi-depot train driver scheduling

Uses Software

• Concorde

Cites Work

• On the set covering polytope. II: Lifting the facets with coefficients in \(\{\) 0,1,2\(\}\)
• Optimizing over the first Chvátal closure
• On the set covering polytope. I: All the facets with coefficients in \(\{\) 0,1,2\(\}\)
• On the 0,1 facets of the set covering polytope
• On the facial structure of the set covering polytope
• Facets and lifting procedures for the set covering polytope
• A Lagrangian-based heuristic for large-scale set covering problems
• Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems
• Solving hard set covering problems
• Exact solutions to linear programming problems
• Algorithms to Separate ${\{0,\frac{1}{2}\}}$ -Chvátal-Gomory Cuts
• A Heuristic Method for the Set Covering Problem
• Algorithms for the set covering problem

This page was built for publication: Computational experience with general cutting planes for the set covering problem