On the SQAP-Polytope

Jünger, Michael and Kaibel, Volker (2000) On the SQAP-Polytope.
Published in: SIAM Journal on Optimization Vol. 11 (2). pp. 444-463.


The study of the QAP-Polytope was started by Rijal (1995), Padberg and Rijal (1996), and Jünger and Kaibel (1996), investigating the structure of the feasible points of a (Mixed) Integer Linear Programming formulation of the QAP that provides good lower bounds by its continious relaxation. Rijal (1995), Padberg and Rijal (1996) propose an alternative (Mixed) Integer Linear Programming formulation for the case that the QAP-instance is symmetric in a certain sense and define analogously the SQAP-Polytope. They give a conjecture about the dimension of that polytope, whose proof is one part of this paper. Moreover, we investigate the trivial faces of the SQAP-Polytope and present a first class of non-trivial facets of it. The polyhedral results are used to compute lower bounds for symmetric QAPs.

Download: [img] Postscript - Preprinted Version
Download (753kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr96-241
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 03 Apr 2003 00:00
Last Modified: 16 Jan 2012 13:43
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/241