An LP-based characterization of solvable QAP instances with chess-board and graded structures
Tóm tắt
The quadratic assignment problem (QAP) is perhaps the most widely studied nonlinear combinatorial optimization problem. It has many applications in various fields, yet has proven to be extremely difficult to solve. This difficulty has motivated researchers to identify special objective function structures that permit an optimal solution to be found efficiently. Previous work has shown that certain such structures can be explained in terms of a mixed 0–1 linear reformulation of the QAP known as the level-1 reformulation–linearization-technique (RLT) form. Specifically, the objective function structures were shown to ensure that a binary optimal extreme point solution exists to the continuous relaxation. This paper extends that work by considering classes of solvable cases in which the objective function coefficients have special chess-board and graded structures, and similarly characterizing them in terms of the level-1 RLT form. As part of this characterization, we develop a new relaxed version of the level-1 RLT form, the structure of which can be readily exploited to study the special instances under consideration.
Tài liệu tham khảo
Adams W, Guignard M, Hahn P, Hightower W (2007) A level-2 reformulation-linearization technique bound for the quadratic assignment problem. Eur J Oper Res 180(3):983–996
Adams W, Johnson T (1994) Improved linear programming-based lower bounds for the quadratic assignment problem. DIMACS Ser Discrete Math Theoret Comput Sci 16:43–75
Adams W, Sherali H (2005) A hierarchy of relaxations leading to the convex hull representation for general discrete optimization problems. Ann Oper Res 140(1):21–47
Adams W, Sherali H (1986) A tight linearization and an algorithm for zero-one quadratic programming problems. Manage Sci 32(10):1274–1290
Adams W, Sherali H (1990) Linearization strategies for a class of zero-one mixed integer programming problems. Oper Res 38(2):217–226
Adams W, Sherali H (1993) Mixed integer bilinear programming problems. Math Program 59(3):279–305
Adams W, Waddell L (2014) Linear programming insights into solvable cases of the quadratic assignment problem. Discret Optim 14:46–60
Anstreicher K, Brixius N, Goux J, Linderoth J (2002) Solving large quadratic assignment problems on computational grids. Math Program 91(3):563–588
Burkard RE, Çela E, Demidenko V, Metelski N, Woeginger G (1997) Perspectives of easy and hard cases of the quadratic assignment problem. SFB Report 104, Institute of Mathematics, Technical University, Graz, Austria
Burkard RE, Çela E, Pardalos P, Pitsoulis L (1998) The quadratic assignment problem. Handb Comb Optim 3:241–338
Burkard RE, Çela E, Rote G, Woeginger G (1998) The quadratic assignment problem with a monotone anti-Monge matrix and a symmetric Toeplitz matrix: easy and hard cases. Math Program 82(1–2):125–158
Burkard RE, Klinz B, Rudolf R (1996) Perspectives of Monge properties in optimization. Discret Appl Math 70:95–161
Burkard RE, Offermann J (1977) Entwurf von Schreibmaschinentastaturen mittels quadratischer Zuordnungsprobleme. Z Oper Res 21:B121–B132
Çela E (1998) The quadratic assignment problem: theory and algorithms. Kluwer Academic Publishers, Dordrecht
Çela E, Deineko VG, Woeginger G (2012) Another well-solvable case of the QAP: Maximizing the job completion time variance. Oper Res Lett 40(6):356–359
Çela E, Deineko VG, Woeginger G (2015) Well-solvable cases of the QAP with block-structured matrices. Discret Appl Math 186:56–65
Deineko VG, Woeginger G (1998) A solvable case of the quadratic assignment problem. Oper Res Lett 22(1):13–17
Dickey J, Hopkins J (1972) Campus building arrangement using TOPAZ. Transp Res 6(1):59–68
Elshafei A (1977) Hospital layout as a quadratic assignment problem. Oper Res Quart 28(1):167–179
Erdoğan G, Tansel B (2006) A note on a polynomial time solvable case of the quadratic assignment problem. Discret Optim 3(4):382–384
Erdoğan G, Tansel B (2011) Two classes of quadratic assignment problems that are solvable as linear assignment problems. Discret Optim 8(3):446–451
Geoffrion A, Graves G (1976) Scheduling parallel production lines with changeover costs: practical applications of a quadratic assignment/LP approach. Oper Res 24(4):595–610
Gonçalves AD, Pessoa AA, Bentes C, Farias R, Drummond LM (2017) A graphics processing unit algorithm to solve the quadratic assignment problem using level-2 reformulation-linearization technique. INFORMS J Comput 29(4):676–687
Hahn PM, Krarup J (2001) A hospital facility problem finally solved. J Intell Manuf 12(5–6):487–496
Hahn PM, Zhu Y-R, Guignard M, Hightower W, Saltzman MJ (2012) A level-3 reformulation-linearization technique bound for the quadratic assignment problem. INFORMS J Comput 24(2):202–209
John M, Karrenbauer A (2019) Dynamic sparsification for quadratic assignment problems. In: Khachay M, Kochetov Y, Pardalos P (eds) Mathematical optimization theory and operations research. MOTOR 2019. Lecture notes in computer science 11548. Springer, Cham
Johnson T (1992) New linear programming-based solution procedures for the quadratic assignment problem, PhD Dissertation, Clemson University
Kabadi SN, Punnen AP (2011) An \(O(n^4)\) algorithm for the QAP linearization problem. Math Oper Res 36(4):754–761
Koopmans T, Beckmann M (1957) Assignment problems and the location of economic activities. Econometrica 25(1):53–76
Krarup J, Pruzan P (1978) Computer-aided layout design. In: Balinski ML, Lemarechal C (eds) Mathematical programming in use. North-Holland Publishing Company, Amsterdam, pp 75–94
Laurent M, Seminaroti M (2015) The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure. Oper Res Lett 43(1):103–109
Loiola EM, Maia de Abreu NM, Boaventura-Netto PO, Hahn PM, Querido T (2007) A survey for the quadratic assignment problem. Eur J Oper Res 176(2):657–690
Pardalos PM, Rendl F, Wolkowicz H (1994) The quadratic assignment problem: a survey and recent developments. DIMACS Ser Discrete Math Theoret Comput Sci 16:1–42
Punnen AP, Kabadi SN (2013) A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems. Discret Optim 10(3):200–209
Sherali H, Adams W (1994) A hierarchy of relaxations and convex hull characterizations for mixed-integer zero-one programming problems. Discret Appl Math 52(1):83–106
Sherali H, Adams W (1990) A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J Discret Math 3(3):411–430
Sherali H, Adams W (1999) A reformulation-linearization technique for solving discrete and continuous nonconvex problems. Kluwer Academic Publishers, Dordrecht/Boston/London
Steinberg L (1961) The backboard wiring problem: a placement algorithm. SIAM Rev 3(1):37–50
Ugi I, Bauer J, Friedrich J, Gasteiger J, Jochum C, Schubert W (1979) Neue anwendungsgebiete für computer in der chemie. Angew Chem 91:99–111
Waddell L, Adams W (2021) Characterizing linearizable QAPs by the level-1 reformulation-linearization technique, http://www.optimization-online.org/DB_FILE/2021/03/8308.pdf