A note on some computationally difficult set covering problems

DOI10.1007/BF01588309MaRDI QIDQ3867546zbMATH OpenFDO

Authors David Avis

Publication date 1980

Published in Mathematical Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01588309

zbMATH Keywords

0-1 programmingbranch-and-bound methodcombinatorial optimizationcomputational complexitycomputationally difficult problemslinear programming relaxationlower bounds, Steiner triple systemsset covering problems

Mathematics Subject Classification ID

Combinatorial aspects of block designs (05B05) Steiner systems in finite geometry (51E10) Numerical mathematical programming methods (65K05) Analysis of algorithms and problem complexity (68Q25) Boolean programming (90C09)

Cites work

• An Improved Implicit Enumeration Approach for Integer Programming
• Determining the Chromatic Number of a Graph
• Determining the Stability Number of a Graph
• scientific article; zbMATH DE number 3550465 (Why is no real title available?)
• scientific article; zbMATH DE number 3583767 (Why is no real title available?)
• scientific article; zbMATH DE number 3410784 (Why is no real title available?)
• Set Covering by Single-Branch Enumeration with Linear-Programming Subproblems

Cited in

(20)

• Solving multiple scenarios in a combinatorial auction
• A probabilistic heuristic for a computationally difficult set covering problem
• A network relaxation based enumeration algorithm for set partitioning
• An interior point algorithm to solve computationally difficult set covering problems
• An exact algorithm for the maximum stable set problem
• The design of a 0-1 integer optimizer and its application in the Carmen system
• A tabu search approach to the constraint satisfaction problem as a general problem solver
• Measuring instance difficulty for combinatorial optimization problems
• An algorithm for large scale 0-1 integer programming with application to airline crew scheduling
• Solving hard set covering problems
• Solving large Steiner Triple Covering Problems
• Solving the non-unicost set covering problem by using cuckoo search and black hole optimization
• A set covering approach for multi-depot train driver scheduling
• Classification of orthogonal arrays by integer programming
• Improved solutions to the Steiner triple covering problem
• Constraint Orbital Branching
• Use of hidden network structure in the set partitioning problem
• Russian doll search for the Steiner triple covering problem
• A biased random-key genetic algorithm for the Steiner triple covering problem
• Surrogate constraint normalization for the set covering problem

This page was built for publication: A note on some computationally difficult set covering problems

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