Tightening a Discrete Formulation of the Quadratic Assignment Problem

Abstract

The quadratic assignment problem is a well studied and notoriously difficult combinatorial problem. Recently, a discrete linear formulation of the quadratic assignment problem was presented that solved five previously unsolved instances from the quadratic assignment library, QAPLIB, to optimality. That formulation worked especially well on sparse instances. In this paper we show how to tighten that formulation by adding cuts to the auxiliary variables. The cuts are derived from solving linear programming problems before solving the main problem. The linear programming problems are easily solved even for larger instances and therefore many cuts can be added without any considerable change of computing time. With only a few cuts we can improve the root node bound considerably.