Three ideas for the Quadratic Assignment Problem

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.)