A benchmark library and a comparison of heuristic methods for the linear ordering problem

被引：33

作者：

Marti, Rafael ^{[1
]}

Reinelt, Gerhard ^{[2
]}

Duarte, Abraham ^{[3
]}

机构：

[1] Univ Valencia, Dept Estadist & Invest Operat, Valencia, Spain

[2] Heidelberg Univ, Inst Comp Sci, Heidelberg, Germany

[3] Univ Rey Juan Carlos, Dept Ciencias Computac, Madrid, Spain

来源：

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS | 2012年 / 51卷 / 03期

关键词：

Metaheuristics; Empirical comparison; Library; SEARCH; ALGORITHM;

D O I：

10.1007/s10589-010-9384-9

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The linear ordering problem consists of finding an acyclic tournament in a complete weighted digraph of maximum weight. It is one of the classical NP-hard combinatorial optimization problems. This paper surveys a collection of heuristics and metaheuristic algorithms for finding near-optimal solutions and reports about extensive computational experiments with them. We also present the new benchmark library LOLIB which includes all instances previously used for this problem as well as new ones.

引用

页码：1297 / 1317

页数：21

共 31 条

[1]

Achatz H., 2006, P ORNEWS, V26, P10

[2]

[Anonymous], 1996, COMPUT OPTIM APPL, DOI DOI 10.1007/BF00249646

[3]

[Anonymous], 2004, J. Math. Model. Algorithms, DOI DOI 10.1023/B:JMMA.0000049426.06305.D8

[4]

[Anonymous], 1993, The Stanford graph base: A platform for combinatorial computing

[5]

[Anonymous], COMPUTER USES SOCIAL

[6]

[Anonymous], 1997, TABU SEARCH

[7]

AUJAC H, 1960, REV EC, V2, P169

[8]

Boenchendorf Konrad., 1982, MATH SYSTEMS EC, V74

[9] An experimental evaluation of a scatter search for the linear ordering problem [J].

Campos, V ;

Glover, F ;

Laguna, M ;

Martí, R .

JOURNAL OF GLOBAL OPTIMIZATION, 2001, 21 (04) :397-414

[10] A survey on the linear ordering problem for weighted or unweighted tournaments [J].

Charon, Irene ;

Hudry, Olivier .

4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2007, 5 (01) :5-60

← 1 2 3 4 →