The QAP-Polytope and the Star-Transformation

Jünger, Michael and Kaibel, Volker (2001) The QAP-Polytope and the Star-Transformation.
Published in: Discrete Applied Mathematics Vol. 111 (3). pp. 283-306.


Polyhedral Combinatorics has been successfully applied to obtain considerable algorithmic progress towards the solution of many prominent hard combinatorial optimization problems. Until very recently, the quadratic assignment problem (QAP) was one of the few exceptions. Recent work of Rijal (1995) and Padberg and Rijal (1996) 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. Moreover, an 'ìnductive construction'' of the QAP-Polytope is derived that might be useful in branch-and-cut algorithms.

Download: [img] Postscript - Preprinted Version
Download (983kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr97-284
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 27 Jun 2003 00:00
Last Modified: 12 Jan 2012 13:03