The QAP-polytope and the star transformation

Polyhedral Combinatorics has been successfully applied to obtain considerab le algorithmic progress towards the solution of many prominent hard combina torial optimization problems. Until a few years ago, the quadratic assignme nt problem (QAP) was one of the exceptions. The work of Padberg and Rijal ( Location, Scheduling, Design and Integer Programming, Kluwer Academic Publi shers, Dordrecht, 1996; Rijal, Ph.D. Thesis, New York University, 1995) has on the one hand yielded some basic facts about the associated quadratic as signment 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 propos e an isomorphic transformation of the "natural" realization of the quadrati c assignment polytope, which simplifies the polyhedral investigations enorm ously. We demonstrate this by giving short proofs of the basic results on t he polytope that indicate that, exploiting the techniques developed in this paper, deeper polyhedral investigations of the QAP now become possible. (C ) 2001 Elsevier Science B.V. All rights reserved.