Solving the quadratic assignment problem by means of general purpose mixed integer linear programming solvers

被引：18
|
作者：
Zhang, Huizhen [1 ,2 ]
Beltran-Royo, Cesar [1 ]
Ma, Liang [2 ]
机构：
[1] Rey Juan Carlos Univ, Madrid, Spain
[2] Univ Shanghai Sci & Technol, Sch Management, Shanghai, Peoples R China
来源：
ANNALS OF OPERATIONS RESEARCH | 2013年 / 207卷 / 01期
基金：
中国国家自然科学基金;
关键词：
Quadratic assignment problem; Mixed integer linear programming; FORMULATION;
D O I：
10.1007/s10479-012-1079-4
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
The Quadratic Assignment Problem (QAP) can be solved by linearization, where one formulates the QAP as a mixed integer linear programming (MILP) problem. On the one hand, most of these linearizations are tight, but rarely exploited within a reasonable computing time because of their size. On the other hand, Kaufman and Broeckx formulation (Eur. J. Oper. Res. 2(3):204-211, 1978) is the smallest of these linearizations, but very weak. In this paper, we analyze how the Kaufman and Broeckx formulation can be tightened to obtain better QAP-MILP formulations. As shown in our numerical experiments, these tightened formulations remain small but computationally effective to solve the QAP by means of general purpose MILP solvers.
引用
收藏
页码：261 / 278
页数：18
相关论文
共 50 条
12345