Polyhedral Combinatorics of QAPs with Less Objects than Locations (Extended Abstract)

Kaibel, Volker (1997) Polyhedral Combinatorics of QAPs with Less Objects than Locations (Extended Abstract).
Technical Report , 10 p.


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.

Download: [img] Postscript
Download (473kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr97-297
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Dec 2011 09:45
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/297