ISSN:
1436-4646
Keywords:
Quadratic assignment problem
;
Lower bounds
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We consider transformations of the (metric) Quadratic Assignment Problem (QAP) that exploit the metric structure of a given instance. We show in particular how the structural properties of rectangular grids can be used to improve a given lower bound. Our work is motivated by previous research of Palubetskes (1988), and it extends a bounding approach proposed by Chakrapani and Skorin-Kapov (1993). Our computational results indicate that the present approach is practical; it has been applied to problems of dimension up ton = 150. Moreover, the new approach yields by far the best lower bounds on most of the instances of metric QAPs that we considered.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01585995
