Three Ideas for the Quadratic Assignment Problem
Matteo Fischetti, Michele Monaci, Domenico Salvagnin
Operations Research · 2012 · Volume 60 · Issue 4
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
Enable JavaScript for citation tools and additional paper interactions.