A note on some computationally difficult set covering problems
From MaRDI portal
Publication:3867546
DOI10.1007/BF01588309zbMath0429.90047MaRDI QIDQ3867546
Publication date: 1980
Published in: Mathematical Programming (Search for Journal in Brave)
computational complexity; combinatorial optimization; 0-1 programming; linear programming relaxation; branch-and-bound method; set covering problems; computationally difficult problems; lower bounds, Steiner triple systems
68Q25: Analysis of algorithms and problem complexity
65K05: Numerical mathematical programming methods
05B05: Combinatorial aspects of block designs
51E10: Steiner systems in finite geometry
90C09: Boolean programming
Related Items
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, 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, A set covering approach for multi-depot train driver scheduling, Classification of orthogonal arrays by integer programming, Constraint Orbital Branching
Cites Work