Optimization Online


A Level-3 Reformulation-linearization Technique Based Bound for the Quadratic Assignment Problem

Peter M. Hahn (hahn***at***seas.upenn.edu)
Yi-Rong Zhu (yrzhu***at***seas.upenn.edu)
Monique Guignard (guignard***at***wharton.upenn.edu)
William L. Hightower (bhightower***at***linus.highpoint.edu)

Abstract: We apply the level-3 Reformulation Linearization Technique (RLT3) to the Quadratic Assignment Problem (QAP). We then present our experience in calculating lower bounds using an essentially new algorithm, based on this RLT3 formulation. This algorithm is not guaranteed to calculate the RLT3 lower bound exactly, but approximates it very closely and reaches it in some instances. For Nugent problem instances up to size 24, our RLT3-based lower bound calculation solves these problem instances exactly or serves to verify the optimal value. Calculating lower bounds for problems sizes larger than size 25 still presents a challenge due to the large memory needed to implement the RLT3 formulation. Our presentation emphasizes the steps taken to significantly conserve memory by using the numerous problem symmetries in the RLT3 formulation of the QAP.

Keywords: Quadratic Assignment, QAP, Reformulation Linearization, RLT, dual ascent, exact solution

Category 1: Combinatorial Optimization (Other )

Category 2: Integer Programming (0-1 Programming )

Citation: University of Pennsylvania, School of Engineering and Applied Science, ESE Department, 200 S. 33rd Street, Philadelphia, PA 19104-6314

Download: [PDF]

Entry Submitted: 09/23/2008
Entry Accepted: 09/24/2008
Entry Last Modified: 07/18/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society