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.
Abstract
For the classical quadratic assignment problem (QAP), where n objects have to be assigned to n locations (the n×ncase), 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×ncase). It turns out that the polytopes that are associated with this variant are quite different from the ones associated with the n×ncase. However, one can obtain structural results on the m×npolytopes by exploiting knowledge on the n×ncase, 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×npolytopes, 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 branchandbound. Moreover, we can calculate for several yet unsolved instances significantly improved lower bounds.
Download: 
Postscript
Download (473kB)  Preview 

Editorial actions:  View Item (Login required) 
Item Type:  Paper (Technical Report) 

Citations:  No citation data. 
Uncontrolled Keywords:  cutting plane algorithms polyhedral combinatorics quadratic assignment problem 
Subjects: 

Divisions:  Institute of Computer Science > Computer Science Department  Prof. Dr. Juenger 
Related URLs: 
ZAIK Number:  zpr97297 

Depositing User:  Archive Admin 
Date Deposited:  02 Apr 2001 00:00 
Last Modified:  19 Dec 2011 09:45 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/297 