A Level-3 Reformulation-Linearization Technique Based Bound for the Quadratic Assignment Problem
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