Computational experience with general cutting planes for the set covering problem

DOI10.1016/J.ORL.2008.09.009MaRDI QIDQ1002077zbMATH OpenOpenAlexFDO

Authors 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 planesexact separationset covering

Mathematics Subject Classification ID

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

Recommendations

• An algorithm for set covering problem
• On the facial structure of the set covering polytope
• Enhancing an algorithm for set covering problems
• The column subtraction algorithm: An exact method for solving weighted set covering, packing and partitioning problems
• An approach to the solution of the set-covering problem

Cites work

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

Cited in

(14)

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

Describes a project that uses

Uses Software

• Concorde

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

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