A NEW EXACT ALGORITHM FOR THE SOLUTION OF QUADRATIC ASSIGNMENT PROBLEMS

被引：32

作者：

MAUTOR, T

ROUCAIROL, C

机构：

[1] INRIA,DOMAINE VOLUCEAU ROCQUENCOURT,BP 105,F-78153 LE CHESNAY,FRANCE

[2] MASI,F-78153 LE CHESNAY,FRANCE

来源：

DISCRETE APPLIED MATHEMATICS | 1994年 / 55卷 / 03期

关键词：

D O I：

10.1016/0166-218X(94)90014-0

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The Quadratic Assignment Problem is known as a combinatorial optimization problem, which is very hard to solve exactly. A survey of recent methods for solving this problem is given. Then an exact algorithm is presented along with computational results on a variety of test problems. This algorithm obtains very good results and, for the first time to our knowledge, solves exactly problems of size up to twenty, this in less than twenty minutes.

引用

页码：281 / 293

页数：13

共 35 条

[1] A HEURISTIC ALGORITHM AND SIMULATION APPROACH TO RELATIVE LOCATION OF FACILITIES [J].

ARMOUR, GC ;

BUFFA, ES .

MANAGEMENT SCIENCE, 1963, 9 (02) :294-309

[2]

BALAS E, 1980, TIMS ORSA M WASHINGT

[3] BENDERS PARTITIONING SCHEME APPLIED TO A NEW FORMULATION OF THE QUADRATIC ASSIGNMENT PROBLEM [J].

BAZARAA, MS ;

SHERALI, HD .

NAVAL RESEARCH LOGISTICS, 1980, 27 (01) :29-41

[4] A BRANCH-AND-BOUND-BASED HEURISTIC FOR SOLVING THE QUADRATIC ASSIGNMENT PROBLEM [J].

BAZARAA, MS ;

KIRCA, O .

NAVAL RESEARCH LOGISTICS, 1983, 30 (02) :287-304

[5] THE ASYMPTOTIC-BEHAVIOR OF QUADRATIC SUM ASSIGNMENT PROBLEMS - A STATISTICAL-MECHANICS APPROACH [J].

BONOMI, E ;

LUTTON, JL .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1986, 26 (02) :295-300

[6]

BROWN D, 1989, 3RD P C GEN ALG ARL, P406

[7]

BUFFA ES, 1962, HARVARD BUS REV, V42, P136

[8]

BURKARD R, 1984, P C MATH PROGRAMMING, P53

[9] A HEURISTIC FOR QUADRATIC BOOLEAN PROGRAMS WITH APPLICATIONS TO QUADRATIC ASSIGNMENT PROBLEMS [J].

BURKARD, RE ;

BONNIGER, T .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1983, 13 (04) :374-386

[10]

BURKARD RE, 1980, ASSIGNMENT MATCHING

← 1 2 3 4 →