Universität zu Köln

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

Preview

PDF zpr96-241.pdf - Submitted Version Download (376kB) | Preview

Abstract

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.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Jünger, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED Kaibel, Volker UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-547600
Journal or Publication Title:	SIAM Journal on Optimization
Volume:	11
Number:	2
Page Range:	pp. 444-463
Date:	2000
Publisher:	SIAM
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/54760