A note on some computationally difficult set covering problems

DOI10.1007/BF01588309zbMath0429.90047MaRDI QIDQ3867546

David Avis

Publication date: 1980

Published in: Mathematical Programming (Search for Journal in Brave)

zbMATH Keywords

computational complexitycombinatorial optimization0-1 programminglinear programming relaxationbranch-and-bound methodset covering problemscomputationally difficult problemslower bounds, Steiner triple systems

Mathematics Subject Classification ID

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

Related Items (20)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Determining the Stability Number of a Graph
• Determining the Chromatic Number of a Graph
• An Improved Implicit Enumeration Approach for Integer Programming
• Set Covering by Single-Branch Enumeration with Linear-Programming Subproblems

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