Network-based formulations of the quadratic assignment problem

被引：7

作者：

Ball, MO ^{[1
]}

Kaku, BK ^{[1
]}

Vakhutinsky, A ^{[1
]}

机构：

[1] Univ Maryland, Coll Business & Management, College Pk, MD 20742 USA

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1998年 / 104卷 / 01期

关键词：

design; facilities; network programming; integer programming;

D O I：

10.1016/S0377-2217(96)00330-X

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

We present two formulations of the Quadratic Assignment Problem (QAP) that result in network Bow problems with integer variables and side constraints. A linearization of the QAP is obtained in both cases by considering each facility to consist of two parts-a source for all outgoing flows from that facility, and a sink for all incoming flows to the facility. Preliminary computational experience with both approaches is presented. (C) 1998 Elsevier Science B.V.

引用

页码：241 / 249

页数：9

共 15 条

[1]

BALAS E, 1975, 457475 WP CARN MELL

[2]

BALAS E, 1980, TIMS ORSA M WASH DC

[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]

BURKARD RE, 1980, LECT NOTES EC MATH S, V184

[6] A NEW LOWER BOUND FOR THE QUADRATIC ASSIGNMENT PROBLEM [J].

CARRARESI, P ;

MALUCELLI, F .

OPERATIONS RESEARCH, 1992, 40 :S22-S27

[7] OPTIMAL AND SUBOPTIMAL ALGORITHMS FOR THE QUADRATIC ASSIGNMENT PROBLEM [J].

GILMORE, PC .

JOURNAL OF THE SOCIETY FOR INDUSTRIAL AND APPLIED MATHEMATICS, 1962, 10 (02) :305-313

[8] AN EXACT ALGORITHM FOR THE GENERAL QUADRATIC ASSIGNMENT PROBLEM [J].

KAKU, BK ;

THOMPSON, GL .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1986, 23 (03) :382-390

[9] ALGORITHM FOR QUADRATIC ASSIGNMENT PROBLEM USING BENDERS DECOMPOSITION [J].

KAUFMAN, L ;

BROECKX, F .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1978, 2 (03) :207-211

[10] THE QUADRATIC ASSIGNMENT PROBLEM [J].

LAWLER, EL .

MANAGEMENT SCIENCE, 1963, 9 (04) :586-599

← 1 2 →