Universität zu Köln

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

Preview

PDF zpr97-284.pdf - Submitted Version Download (364kB) | Preview

Abstract

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.

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-547913
Journal or Publication Title:	Discrete Applied Mathematics
Volume:	111
Number:	3
Page Range:	pp. 283-306
Date:	2001
Publisher:	Elsevier
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/54791