• Wrong document? Swap it for free
  • Written by students who passed
  • Immediately available after payment
  • Read online or as PDF
Sell
Where do you study
Your language
Document preview thumbnail
Preview 3 out of 18 pages
Exam (elaborations)

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

Document preview thumbnail
Preview 3 out of 18 pages

A Level-3 Reformulation-Linearization Technique Based Bound for the Quadratic Assignment Problem by Peter M. Hahn1 Electrical and Systems Engineering, The University of Pennsylvania Philadelphia, PA , USA Yi-Rong Zhu Electrical and Systems Engineering, The University of Pennsylvania Philadelphia, PA , USA Monique Guignard OPIM Department, The University of Pennsylvania Philadelphia, PA , USA William L. Hightower Mathematics and Computer Science, High Point University High Point, NC 27262, USA 1 1Corresponding author (Current address: 2127 Tryon Street, Philadelphia, PA , USA). Abstract: We apply the level-3 R eformulation L inearization T echnique (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. Key words: Quadratic Assignment, QAP, Reformulation Linearization, RLT, dual ascent, exact solution. Acknowledgements: This material is based upon work supported by the National Science Foundation under grant No. DMI-0400155. The authors are grateful to management and consulting staff of the San Diego Supercomputing Center for the invaluable computational resources and guidance they provided for this work. We thank Professor Matthew Saltzman of the Mathematics Department at Clemson University for his expert advice on computational optimization matters. Calculation of large RLT3-based QAP lower bounds was made possible by advanced computational resources deployed and maintained by Clemson Computing and Information Technology and the Clemson University International Center for Automotive Research Center for Computational Mobility Systems. The authors acknowledge the kind and competent assistance of the staff at the Cyber Infrastructure Technology Integration group. We also thank J. Barr von Oehsen, Director, Computational Science, Cyberinfrastructure Technology Integration at Clemson University for his help in adapting our code to the Sun Fire E6900 server. 2 Notation Entries of a matrix E of size mxnx…xp, indexed by i,j,…,k, are denoted eij…k. Conversely, given numbers , one can form a corresponding matrix the optimal value of optimization problem (P). 1. Introduction of appropriate size. Z(P) will denote The quadratic assignment problem (QAP) is known as one of the most interesting and challenging problems in combinatorial optimization. It finds applications in facility location, computer manufacturing, scheduling, building layout design, and process communications. The standard mathematical formulation of the QAP is where The QAP optimizes a quadratic function over the set of permutation matrices no quadratic term if in the objective function when or (1-a) . (1-b) . Notice there is since the constraints force and , and otherwise. The QAP is one of the most difficult NP-hard combinatorial optimization problems, and instances of size can usually not be solved in reasonable CPU time. In addition the majority of QAP test problems have a homogeneous objective function, and this contributes to their difficulty, as this tends to produce weak lower bounds. Recent developments have produced improved, that is, tighter, bounds. The new methodologies include the interior point bound by Resende et al. (1995), the level-1 RLT-based dual-ascent bound by Hahn and Grant (1998), the dual-based bound by Karisch et al. (1999), the convex quadratic programming bound by Anstreicher and Brixius (2001), the level-2 RLT interior point bound by Ramakrishnan et al. (2002), the SDP bound by Roupin (2004), the lift-and-project SDP bound by Burer and Vandenbussche (2006), the bundle method bound by Rendl and Sotirov (2007), and the Hahn Hightower level-2 RLT-based dual-ascent bound by Adams et al. (2007). The tightest bounds are the lift-and-project SDP bound and the two level-2 RLT-based bounds. However, when taking speed and efficiency into consideration, the most competitive bounds are the level-1 RLT based dual-ascent bound by Hahn and Grant (1998), the convex quadratic programming bound by Anstreicher and Brixius (2001), and the Hahn-Hightower level-2 RLT-based dual-ascent bound by Adams et al. (2007). The reformulation-linearization technique (RLT) is a strategy developed by (Adams and Sherali 1986, 1990; Sherali and Adams 1990, 1994, Sherali and Adams 1998, 1999) for generating tight linear programming relaxations for discrete and continuous nonconvex problems. For mixed zero-one programs involving binary variables, RLT establishes an 3 level hierarchy of relaxations spanning from the ordinary linear programming relaxation to the convex hull of feasible integer solutions. For a given , the level-d RLT, or simply, RLTd, constructs various polynomial factors of degree consisting of the product of some binary variables or their complements steps. First it reformulates . The proced


Document information

Uploaded on
July 26, 2024
Number of pages
18
Written in
2023/2024
Type
Exam (elaborations)
Contains
Questions & answers
$16.99

Wrong document? Swap it for free Within 14 days of purchase and before downloading, you can choose a different document. You can simply spend the amount again.
Written by students who passed
Immediately available after payment
Read online or as PDF

Seller avatar
Reputation scores are based on the amount of documents a seller has sold for a fee and the reviews they have received for those documents. There are three levels: Bronze, Silver and Gold. The better the reputation, the more your can rely on the quality of the sellers work.
Sold
215
Followers
44
Items
2637
Last sold
2 weeks ago



Why students choose Stuvia

Created by fellow students, verified by reviews

Quality you can trust: written by students who passed their tests and reviewed by others who've used these notes.

Didn't get what you expected? Choose another document

No worries! You can instantly pick a different document that better fits what you're looking for.

Pay as you like, start learning right away

No subscription, no commitments. Pay the way you're used to via credit card and download your PDF document instantly.

Student with book image

“Bought, downloaded, and aced it. It really can be that simple.”

Alisha Student

Working on your references?

Create accurate citations in APA, MLA and Harvard with our free citation generator.

Working on your references?

Frequently asked questions

Whoops! We can’t load your doc right now. Try again or contact support.