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 条
  • [31] Bivium as a Mixed-Integer Linear Programming Problem
    Borghoff, Julia
    Knudsen, Lars R.
    Stolpe, Mathias
    CRYPTOGRAPHY AND CODING, PROCEEDINGS, 2009, 5921 : 133 - 152
  • [32] Constraint Logic Programming and Integer Programming approaches and their collaboration in solving an assignment scheduling problem
    Darby-Dowman K.
    Little J.
    Mitra G.
    Zaffalon M.
    Constraints, 1997, 1 (3) : 245 - 264
  • [33] Automated Configuration of Mixed Integer Programming Solvers
    Hutter, Frank
    Hoos, Holger H.
    Leyton-Brown, Kevin
    INTEGRATION OF AI AND OR TECHNIQUES IN CONSTRAINT PROGRAMMING FOR COMBINATORIAL OPTIMIZATION PROBLEMS, 2010, 6140 : 186 - 202
  • [34] Bilevel Mixed-Integer Linear Programming Model for Solving the Single Airport Location Problem
    Hammad, Ahmed W. A.
    Akbarnezhad, Ali
    Rey, David
    JOURNAL OF COMPUTING IN CIVIL ENGINEERING, 2017, 31 (05)
  • [35] Solving the Quadratic Assignment Problem
    Sergienko, I., V
    Shylo, V. P.
    Chupov, S., V
    Shylo, P., V
    CYBERNETICS AND SYSTEMS ANALYSIS, 2020, 56 (01) : 53 - 57
  • [36] Solving the Quadratic Assignment Problem
    I. V. Sergienko
    V. P. Shylo
    S. V. Chupov
    P. V. Shylo
    Cybernetics and Systems Analysis, 2020, 56 : 53 - 57
  • [37] Embedding of linear programming in a simulated annealing algorithm for solving a mixed integer production planning problem
    Teghem, J
    Pirlot, M
    Antoniadis, C
    JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 1995, 64 (1-2) : 91 - 102
  • [38] General-Purpose Linear Solvers
    Dyer, Stephen A.
    IEEE INSTRUMENTATION & MEASUREMENT MAGAZINE, 2015, 18 (03) : 22 - 27
  • [39] Linear programming insights into solvable cases of the quadratic assignment problem
    Adams, Warren
    Waddell, Lucas
    DISCRETE OPTIMIZATION, 2014, 14 : 46 - 60
  • [40] An algorithm for solving multiple objective integer linear programming problem
    Abbas, M
    Chaabane, D
    RAIRO-OPERATIONS RESEARCH, 2002, 36 (04): : 351 - 364
12345