Universität zu Köln

Kaibel, Volker (1997). Polyhedral Combinatorics of QAPs with Less Objects than Locations (Extended Abstract). Working Paper.

Preview

PDF zpr97-297.pdf - Draft Version Download (219kB) | Preview

Abstract

For the classical quadratic assignment problem (QAP), where n objects have to be assigned to n locations (the n×n-case), polyhedral studies have been started in the very recent years by several authors. In this paper, we investigate the variant of the QAP, where the number of locations may exceed the number of objects (the m×n-case). It turns out that the polytopes that are associated with this variant are quite different from the ones associated with the n×n-case. However, one can obtain structural results on the m×n-polytopes by exploiting knowledge on the n×n-case, since the first ones are certain projections of the latter ones. Besides answering the basic questions for the affine hulls, the dimensions, and the trivial facets of the m×n-polytopes, we present a large class of facet defining inequalities. Employed into a cutting plane procedure, these polyhedral results enable us to compute optimal solutions for some hard instances from the QAPLIB for the first time without using branch-and-bound. Moreover, we can calculate for several yet unsolved instances significantly improved lower bounds.

Item Type:	Preprints, Working Papers or Reports (Working Paper)
Creators:	Creators Email ORCID ORCID Put Code Kaibel, Volker UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-548140
Date:	1997
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/54814