Three Ideas for the Quadratic Assignment Problem
- 1 August 2012
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 60 (4) , 954-964
Abstract
We address the exact solution of the famous esc instances of the quadratic assignment problem. These are extremely hard instances that remained unsolved—even allowing for a tremendous computing power—by using all previous techniques from the literature. During this challenging task we found that three ideas were particularly useful and qualified as a breakthrough for our approach. The present paper is about describing these ideas and their impact in solving esc instances. Our method was able to solve, in a matter of seconds or minutes on a single PC, all easy cases (all esc16* plus esc32e and esc32g). The three very hard instances esc32c, esc32d, and esc64a were solved in less than half an hour, in total, on a single PC. We also report the solution, in about five hours, of tai64c. By using a facility-flow splitting procedure, we were also able to solve to proven optimality, for the first time, esc32h (in about two hours) as well as “the big fish” esc128. (To our great surprise, the solution of the latter required just a few seconds on a single PC.)Keywords
This publication has 23 references indexed in Scilit:
- Faster integer-feasibility in mixed-integer linear programs by branching to force changeComputers & Operations Research, 2011
- Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetryMathematical Programming, 2010
- Orbital branchingMathematical Programming, 2009
- Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problemMathematical Programming, 2008
- A new linearization method for quadratic assignment problemsOptimization Methods and Software, 2006
- Active-constraint variable ordering for faster feasibility of mixed integer linear programsMathematical Programming, 2006
- Pruning by isomorphism in branch-and-cutMathematical Programming, 2002
- Solving large quadratic assignment problems on computational gridsMathematical Programming, 2002
- An algorithm for the quadratic assignment problem using Bender's decompositionEuropean Journal of Operational Research, 1978
- Assignment Problems and the Location of Economic ActivitiesEconometrica, 1957