A probabilistic heuristic for a computationally difficult set covering problem

✍ Scribed by Thomas A Feo; Mauricio G.C Resende

• Publisher: Elsevier Science
• Year: 1989
• Tongue: English
• Weight: 319 KB
• Volume: 8
• Category: Article
• ISSN: 0167-6377
• DOI: 10.1016/0167-6377(89)90002-3

✦ Synopsis

An efficient probabilistic set covering heuristic is presented. The heuristic is evaluated on empirically difficult to solve set covering problems that arise from Steiner triple systems. The optimal solution to only a few of these instances is known. The heuristic provides these solutions as well as the best known solutions to all other instances attempted.algorithms * heuristic * tests * integer programming * set covering