Linear programming insights into solvable cases of the quadratic assignment problem

Koopmans, 1957, Assignment problems and the location of economic activities, Econometrica, 25, 53, 10.2307/1907742 Burkard, 1998, The quadratic assignment problem, vol. 3 Çela, 1998 Loiola, 2007, A survey for the quadratic assignment problem, European J. Oper. Res., 176, 657, 10.1016/j.ejor.2005.09.032 Steinberg, 1961, The backboard wiring problem: a placement algorithm, SIAM Rev., 3, 37, 10.1137/1003003 Dickey, 1972, Campus building arrangement using TOPAZ, Transp. Res., 6, 59, 10.1016/0041-1647(72)90111-6 Burkard, 1977, Entwurf von Schreibmaschinentastaturen mittels quadratischer Zuordnungsprobleme, Z. Oper. Res., 21, B121 Elshafei, 1977, Hospital layout as a quadratic assignment problem, Oper. Res. Q., 28, 167, 10.1057/jors.1977.29 Geoffrion, 1976, Scheduling parallel production lines with changeover costs: practical applications of a quadratic assignment/LP approach, Oper. Res., 24, 595, 10.1287/opre.24.4.595 Ugi, 1979, Neue anwendungsgebiete für computer in der chemie, Angew. Chem., 91, 99, 10.1002/ange.19790910204 Krarup, 1978, Computer-aided layout design, 10.1007/BFb0120827 Burkard, 1997, QAPLIB - a quadratic assignment program library, J. Global Optim., 10, 391, 10.1023/A:1008293323270 Nugent, 1968, An experimental comparison of techniques for the assignment of facilities to locations, Oper. Res., 16, 150, 10.1287/opre.16.1.150 Adams, 2007, A level-2 reformulation-linearization technique bound for the quadratic assignment problem, European J. Oper. Res., 180, 984, 10.1016/j.ejor.2006.03.051 Anstreicher, 2002, Solving large quadratic assignment problems on computational grids, Math. Program., 91, 563, 10.1007/s101070100255 Hahn, 2001, A hospital facility problem finally solved, J. Intell. Manuf., 12, 487, 10.1023/A:1012252420779 Hahn, 2012, A level-3 reformulation-linearization technique bound for the quadratic assignment problem, INFORMS J. Comput., 24, 202, 10.1287/ijoc.1110.0450 Erdoğan, 2011, Two classes of quadratic assignment problems that are solvable as linear assignment problems, Discrete Optim., 8, 446, 10.1016/j.disopt.2011.03.002 Kabadi, 2011, An O(n4) algorithm for the QAP linearization problem, Math. Oper. Res., 36, 754, 10.1287/moor.1110.0509 Punnen, 2013, A linear time algorithm for the Koopmans–Beckmann QAP linearization and related problems, Discrete Optim., 10, 200, 10.1016/j.disopt.2013.02.003 Burkard, 1998, The quadratic assignment problem with a monotone anti-Monge matrix and a symmetric Toeplitz matrix: easy and hard cases, Math. Program., 82, 125, 10.1007/BF01585868 Deineko, 1998, A solvable case of the quadratic assignment problem, Oper. Res. Lett., 22, 13, 10.1016/S0167-6377(97)00047-3 Çela, 2012, Another well-solvable case of the QAP: maximizing the job completion time variance, Oper. Res. Lett., 40, 356, 10.1016/j.orl.2012.06.005 Wei, 2013, Optimal sequencing of a set of positive numbers with the variance of the sequence’s partial sums maximized, Optim. Lett., 7, 1071, 10.1007/s11590-012-0449-9 Erdoğan, 2006, A note on a polynomial time solvable case of the quadratic assignment problem, Discrete Optim., 3, 382, 10.1016/j.disopt.2006.04.001 Çela, 2011, The Wiener maximum quadratic assignment problem, Discrete Optim., 8, 411, 10.1016/j.disopt.2011.02.002 Burkard, 1997 Burkard, 1998, A unified approach to simple special cases of extremal permutation problems, Optimization, 44, 123, 10.1080/02331939808844404 Adams, 1994, Improved linear programming-based lower bounds for the quadratic assignment problem, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 16, 43, 10.1090/dimacs/016/02 Assad, 1985, On lower bounds for a class of quadratic 0–1 programs, Oper. Res. Lett., 4, 175, 10.1016/0167-6377(85)90025-2 Bazaraa, 1980, Benders’ partitioning scheme applied to a new formulation of the quadratic assignment problem, Naval Res. Logist. Q., 27, 29, 10.1002/nav.3800270104 Frieze, 1983, On the quadratic assignment problem, Discrete Appl. Math., 5, 89, 10.1016/0166-218X(83)90018-5 Kaufman, 1978, An algorithm for the quadratic assignment problem using Benders’ decomposition, European J. Oper. Res., 2, 207, 10.1016/0377-2217(78)90095-4 Lawler, 1963, The quadratic assignment problem, Manag. Sci., 19, 586, 10.1287/mnsc.9.4.586 Adams, 1986, A tight linearization and an algorithm for zero–one quadratic programming problems, Manag. Sci., 32, 1274, 10.1287/mnsc.32.10.1274 Adams, 1990, Linearization strategies for a class of zero–one mixed integer programming problems, Oper. Res., 38, 217, 10.1287/opre.38.2.217 Sherali, 1990, A hierarchy of relaxations between the continuous and convex hull representations for zero–one programming problems, SIAM J. Discrete Math., 3, 411, 10.1137/0403036 Sherali, 1994, A hierarchy of relaxations and convex hull characterizations for mixed-integer zero–one programming problems, Discrete Appl. Math., 52, 83, 10.1016/0166-218X(92)00190-W Sherali, 1999 Nemhauser, 1988 Schrijver, 1986