Three Ideas for the Quadratic Assignment Problem

Matteo Fischetti (), Michele Monaci () and Domenico Salvagnin ()
Additional contact information
Matteo Fischetti: Department of Information Engineering, University of Padova, 35131 Padova, Italy
Michele Monaci: Department of Information Engineering, University of Padova, 35131 Padova, Italy
Domenico Salvagnin: Department of Information Engineering, University of Padova, 35131 Padova, Italy

Operations Research, 2012, vol. 60, issue 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: integer programming; quadratic assignment problem (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1120.1073 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:60:y:2012:i:4:p:954-964

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().