ENHANCING AN ALGORITHM FOR SET COVERING PROBLEMS

被引：101

作者：

BEASLEY, JE ^{[1
]}

JORNSTEN, K ^{[1
]}

机构：

[1] NORWEGIAN SCH ECON & BUSINESS ADM,INST FINANCE & MANAGEMENT SCI,N-5035 BERGEN,NORWAY

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1992年 / 58卷 / 02期

关键词：

SET COVERING; LAGRANGEAN HEURISTIC; F-CUTS;

D O I：

10.1016/0377-2217(92)90215-U

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this note we present enhancements to a previously published algorithm for the optimal solution of set covering problems. These enhancements relate to the use of a Lagrangean heuristic, feasible solution exclusion constraints, Gomory f-cuts and an improved branching strategy. Computational results, for problems involving up to 400 rows and 4000 columns, indicate that the enhanced algorithm gives better computational results than the original algorithm.

引用

页码：293 / 300

页数：8

共 53 条

[1]

ABOUDI R, 1988, SOME EXTENSIONS PIVO

[2] A NETWORK RELAXATION BASED ENUMERATION ALGORITHM FOR SET PARTITIONING [J].

ALI, AI ;

THIAGARAJAN, H .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1989, 38 (01) :76-85

[3] EFFICIENT HEURISTIC SOLUTIONS TO AN AIRLINE CREW SCHEDULING PROBLEM [J].

BAKER, EK ;

BODIN, LD ;

FINNEGAN, WF ;

PONDER, RJ .

AIIE TRANSACTIONS, 1979, 11 (02) :79-85

[4] ON THE SET COVERING POLYTOPE .1. ALL THE FACETS WITH COEFFICIENTS IN (0, 1, 2) [J].

BALAS, E ;

NG, SM .

MATHEMATICAL PROGRAMMING, 1989, 43 (01) :57-69

[5]

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

[6] ON THE SET COVERING POLYTOPE .2. LIFTING THE FACETS WITH COEFFICIENTS IN (0,1,2) [J].

BALAS, E ;

NG, SM .

MATHEMATICAL PROGRAMMING, 1989, 45 (01) :1-20

[7] ON INTEGER-PROGRAM FOR DELIVERY PROBLEM [J].

BALINSKI, ML ;

QUANDT, RE .

OPERATIONS RESEARCH, 1964, 12 (02) :300-&

[8] A GUARANTEED-ACCURACY ROUND-OFF ALGORITHM FOR CYCLIC SCHEDULING AND SET COVERING [J].

BARTHOLDI, JJ .

OPERATIONS RESEARCH, 1981, 29 (03) :501-510

[9]

BEASLEY JE, 1990, NAV RES LOG, V37, P151, DOI 10.1002/1520-6750(199002)37:1<151::AID-NAV3220370110>3.0.CO

[10]

2-2

← 1 2 3 4 5 6 →