Solution techniques for the large set covering problem

DOI10.1016/j.dam.2006.04.043zbMath1147.68091OpenAlexW2130863730MaRDI QIDQ868387

Philippe Galinier, Alain Hertz

Publication date: 2 March 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2006.04.043

zbMATH Keywords

set coveringconstraint satisfaction\(k\)-colouringirreducible infeasible sets

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Approximation methods and heuristics in mathematical programming (90C59) Extremal set theory (05D05) Combinatorial aspects of packing and covering (05B40)

Related Items

Finding Guaranteed MUSes Fast ⋮ Efficient algorithms for finding critical subgraphs ⋮ A new approach for solving set covering problem using jumping particle swarm optimization method ⋮ Using heuristics to find minimal unsatisfiable subformulas in satisfiability problems

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Using tabu search techniques for graph coloring
• Irreducibly inconsistent systems of linear inequalities
• Boosting complete techniques thanks to local search methods
• Finding the minimum weight IIS cover of an infeasible system of linear inequalities
• An effective polynomial-time heuristic for the minimum-cardinality IIS set-covering problem
• Efficient algorithms for finding critical subgraphs
• Detecting IIS in infeasible linear programmes using techniques from goal programming
• Fast Heuristics for the Maximum Feasible Subsystem Problem
• Locating Minimal Infeasible Constraint Sets in Linear Programs
• Finding a Useful Subset of Constraints for Analysis in an Infeasible Linear Program
• Analyzing Infeasible Mixed-Integer and Integer Linear Programs
• Finding the chromatic number by means of critical graphs
• Consistency restoration and explanations in dynamic CSPs---Application to configuration