A PROBABILISTIC HEURISTIC FOR A COMPUTATIONALLY DIFFICULT SET COVERING PROBLEM

被引：600

作者：

FEO, TA ^{[1
]}

RESENDE, MGC ^{[1
]}

机构：

[1] UNIV CALIF BERKELEY,BERKELEY,CA 94720

来源：

OPERATIONS RESEARCH LETTERS | 1989年 / 8卷 / 02期

关键词：

Optimization - Probability - Systems Science and Cybernetics--Heuristic Programming;

D O I：

10.1016/0167-6377(89)90002-3

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页码：67 / 71

页数：5

共 13 条

[1] A NOTE ON SOME COMPUTATIONALLY DIFFICULT SET COVERING PROBLEMS [J].

AVIS, D .

MATHEMATICAL PROGRAMMING, 1980, 18 (02) :138-145

[2]

BALAS E, 1980, MATH PROGRAM STUD, V12, P37, DOI 10.1007/BFb0120886

[3]

BARD JF, 1987, OPERATIONS SEQUENCIN

[4]

BARD JF, 1987, MINIMIZING ACQUISITI

[5]

Chvatal V., 1979, Mathematics of Operations Research, V4, P233, DOI 10.1287/moor.4.3.233

[6]

FEO TA, 1987, NETWORK APPROACH FLI

[7]

Fulkerson D.R., 1974, MATH PROGRAMMING STU, V2, P72

[8]

Garey M. R., 1979, COMPUTERS INTRACTABI

[9] AN IMPROVED IMPLICIT ENUMERATION APPROACH FOR INTEGER PROGRAMMING [J].

GEOFFRIO.AM .

OPERATIONS RESEARCH, 1969, 17 (03) :437-&

[10]

Hall M., 1967, COMBINATORIAL THEORY

← 1 2 →