The QAP-polytope and the star transformation Original Research Article

Polyhedral Combinatorics has been successfully applied to obtain considerable algorithmic progress towards the solution of many prominent hard combinatorial optimization problems. Until a few years ago, the quadratic assignment problem (QAP) was one of the exceptions. The work of Padberg and Rijal (Location, Scheduling, Design and Integer Programming, Kluwer Academic Publishers, Dordrecht, 1996; Rijal, Ph.D. Thesis, New York University, 1995) has on the one hand yielded some basic facts about the associated quadratic assignment polytope, but has on the other hand shown that investigations even of the very basic questions (like the dimension, the affine hull, and the trivial facets) soon become extremely complicated. In this paper, we propose an isomorphic transformation of the “natural” realization of the quadratic assignment polytope, which simplifies the polyhedral investigations enormously. We demonstrate this by giving short proofs of the basic results on the polytope that indicate that, exploiting the techniques developed in this paper, deeper polyhedral investigations of the QAP now become possible.