Optimization Online


Memory-Aware Parallelized RLT3 for Solving Quadratic Assignment Problems

Peter Hahn(hahn***at***seas.upenn.edu)
Amir Roth(roth.amir***at***gmail.com)
Matthew Saltzman(mjs***at***clemson.edu)
Monique Guignard(guignard_monique***at***yahoo.fr)

Abstract: We present a coarse-grain (outer-loop) parallel implementation of RLT1/2/3 (Level 1, 2, and 3 Reformulation and Linearization Technique—in that order) bound calculations for the QAP within a branch-and-bound procedure. For a search tree node of size S, each RLT3 and RLT2 bound calculation iteration is parallelized S ways, with each of S processors performing O(S5) and O(S3) linear assignment problem solution calculations, respectively. Our implementation is aware of memory usage and availability and uses this information to throttle parallelism as appropriate and to manage resources during the branch-and-bound search. Our new code succeeded in solving for the first time the Tai30b instance of the QAP.

Keywords: quadratic assignment, integer programming, reformulation linearization

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Optimization Software and Modeling Systems (Parallel Algorithms )

Category 3: Combinatorial Optimization (Other )

Citation: submitted

Download: [PDF]

Entry Submitted: 11/30/2013
Entry Accepted: 12/01/2013
Entry Last Modified: 11/30/2013

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 Optimization Society