• ¿Documento equivocado? Cámbialo gratis
  • Escrito por estudiantes que aprobaron
  • Inmediatamente disponible después del pago
  • Leer en línea o como PDF
Vender
¿Dónde estudias?
Tu idioma
Document preview thumbnail
Vista previa 3 fuera de 18 páginas
Examen

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

Document preview thumbnail
Vista previa 3 fuera de 18 páginas

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


Información del documento

Subido en
26 de julio de 2024
Número de páginas
18
Escrito en
2023/2024
Tipo
Examen
Contiene
Preguntas y respuestas
$16.99

¿Documento equivocado? Cámbialo gratis Dentro de los 14 días posteriores a la compra y antes de descargarlo, puedes elegir otro documento. Puedes gastar el importe de nuevo.
Escrito por estudiantes que aprobaron
Inmediatamente disponible después del pago
Leer en línea o como PDF

Seller avatar
Los indicadores de reputación están sujetos a la cantidad de artículos vendidos por una tarifa y las reseñas que ha recibido por esos documentos. Hay tres niveles: Bronce, Plata y Oro. Cuanto mayor reputación, más podrás confiar en la calidad del trabajo del vendedor.
Vendido
215
Seguidores
44
Artículos
2637
Última venta
2 semanas hace



Por qué los estudiantes eligen Stuvia

Creado por compañeros estudiantes, verificado por reseñas

Calidad en la que puedes confiar: escrito por estudiantes que aprobaron y evaluado por otros que han usado estos resúmenes.

¿No estás satisfecho? Elige otro documento

¡No te preocupes! Puedes elegir directamente otro documento que se ajuste mejor a lo que buscas.

Paga como quieras, empieza a estudiar al instante

Sin suscripción, sin compromisos. Paga como estés acostumbrado con tarjeta de crédito y descarga tu documento PDF inmediatamente.

Student with book image

“Comprado, descargado y aprobado. Así de fácil puede ser.”

Alisha Student

Preguntas frecuentes

Ups! No podemos cargar tu documento ahora. Inténtalo de nuevo o contacta con soporte.