A Basic Study of the QAP-Polytope

Jünger, Michael and Kaibel, Volker (1996) A Basic Study of the QAP-Polytope.
Technical Report , 20 p.


We investigate a polytope (the 'QAP-Polytope') beyond a 'natural' integer programming formulation of the Quadratic Assignment Problem (QAP) that has been used successfully in order to compute good lower bounds for the QAP in the very recent years. We present basic structural properties of the QAP-Polytope, partially independently also obtained by Rijal (1995). The main original contribution of this work is the representation of the QAP-Polytope in a space different from the one in which it is defined naturally. This representation provides us with a much simpler way to derive the dimension of the QAP-Polytope, as well as to investigate the facial structure of it. Furthermore, it leads to some interesting observations concerning the combinatorial structure of the QAP-Polytope.

Download: [img] Postscript
Download (547kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr96-215
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Jan 2012 10:22
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/215