A Restricted Dual Peaceman-Rachford Splitting Method for a Strengthened DNN Relaxation for QAP

References

• Anjos A, Lasserre J, eds. (2011) Handbook on Semidefinite, Conic and Polynomial Optimization. International Series in Operations Research & Management Science (Springer-Verlag, Berlin).Google Scholar
• Anstreicher K, Brixius N (2000) Solving quadratic assignment problems using convex quadratic programming relaxations. Technical report, University of Iowa, Iowa City.Google Scholar
• Barvinok A, Stephen T (2003) The distribution of values in the quadratic assignment problem. Math. Oper. Res. 28(1):64–91.Link, Google Scholar
• Bashiri M, Karimi H (2012) Effective heuristics and meta-heuristics for the quadratic assignment problem with tuned parameters and analytical comparisons. J. Industrial Engrg. Internat. 8(1):6.Crossref, Google Scholar
• Bhati R, Rasool A (2014) Quadratic assignment problem and its relevance to the real world: A survey. Internat. J. Comput. Appl. 96(9):42–47.Google Scholar
• Birkoff G (1946) Tres observaciones sobre el algebra lineal. Univ. Nac. Tucuman Rev. Ser. A 5:147–151.Google Scholar
• Boley D (2013) Local linear convergence of the alternating direction method of multipliers on quadratic or linear programs. SIAM J. Optim. 23(4):2183–2207.Crossref, Google Scholar
• Bravo Ferreira J, Khoo Y, Singer A (2018) Semidefinite programming approach for the quadratic assignment problem with a sparse graph. Comput. Optim. Appl. 69(3):677–712.Crossref, Google Scholar
• Burkard R, Karisch S, Rendl F (1991) QAPLIB: A quadratic assignment problem library. Eur. J. Oper. Res. 55:115–119.Crossref, Google Scholar
• Çela E (1998) The Quadratic Assignment Problem, vol. 1 of Combinatorial Optimization (Kluwer Academic Publishers, Dordrecht, Germany).Crossref, Google Scholar
• Chen Y, Ye X (2011) Projection onto a simplex. Preprint, submitted February 10, https://arxiv.org/abs/1101.6081.Google Scholar
• Commander C (2003) A survey of the quadratic assignment problem, with applications. PhD thesis, University of Florida, Gainesville.Google Scholar
• Date K, Nagi R (2019) Level 2 reformulation linearization technique-based parallel algorithms for solving large quadratic assignment problems on graphics processing unit clusters. INFORMS J. Comput. 31(4):771–789.Link, Google Scholar
• Davis D, Yin W (2017) Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions. Math. Oper. Res. 42(3):783–805.Link, Google Scholar
• Deng W, Yin W (2016) On the global and linear convergence of the generalized alternating direction method of multipliers. J. Sci. Comput. 66(3):889–916.Crossref, Google Scholar
• Drezner Z (2003) A new genetic algorithm for the quadratic assignment problem. INFORMS J. Comput. 15(3):320–330.Link, Google Scholar
• Drusvyatskiy D, Wolkowicz H (2017) The many faces of degeneracy in conic optimization. Foundations Trends Optim. 3(2):77–170.Crossref, Google Scholar
• Edwards C (1977) The derivation of a greedy approximator for the Koopmans-Beckmann quadratic assignment problem. Proc. CP77 Combinatorial Prog. Conf., Liverpool, 55–86.Google Scholar
• Elshafei A (1977) Hospital layout as a quadratic assignment problem. Oper. Res. Quart. 28:167–179.Crossref, Google Scholar
• Gambardella L, Taillard É, Dorigo M (1999) Ant colonies for the quadratic assignment problem. J. Oper. Res. Soc. 50(2):167–176.Crossref, Google Scholar
• Garey MR, Johnson DS (1979) Computers and Intractability (W. H. Freeman and Company, San Francisco).Google Scholar
• Geoffrion A, Graves G (1976) Scheduling parallel production lines with changeover costs: Practical applications of a quadratic assignment/LP approach. Oper. Res. 24:595–610.Link, Google Scholar
• Goemans M, Williamson D (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6):1115–1145.Crossref, Google Scholar
• Graham N, Hu H, Im J, Li X, Wolkowicz H (2021) rPRSM Version v1.0 http://dx.doi.org/10.5281/zenodo.5709968, https://github.com/INFORMSJoC/2020.0336.Google Scholar
• Gu Y, Jiang B, Han D (2015) An indefinite-proximal-based strictly contractive Peaceman-Rachford splitting method. Preprint, submitted January 1, 2021, https://arxiv.org/abs/1506.02221.Google Scholar
• Hahn P, Zhu YR, Guignard M, Smith J (2010) Exact solution of emerging quadratic assignment problems. Internat. Trans. Oper. Res. 17(5):525–552.Crossref, Google Scholar
• Han D, Yuan X (2013) Local linear convergence of the alternating direction method of multipliers for quadratic programs. SIAM J. Numer. Anal. 51(6):3446–3457.Crossref, Google Scholar
• Han D, Sun D, Zhang L (2018) Linear rate convergence of the alternating direction method of multipliers for convex composite programming. Math. Oper. Res. 43(2):622–637.Link, Google Scholar
• He B, Yuan X (2012) On the o(1/n) convergence rate of the Douglas-Rachford alternating direction method. SIAM J. Numerical Anal. 50(2):700–709.Crossref, Google Scholar
• He B, Yuan X (2015) On non-ergodic convergence rate of Douglas-Rachford alternating direction method of multipliers. Numerische Mathematik 130(3):567–577.Crossref, Google Scholar
• He Y, Li H, Liu X (2018) Relaxed inertial proximal Peaceman-Rachford splitting method for separable convex programming. Frontiers Math. China 13(3):555–578.Crossref, Google Scholar
• He B, Liu H, Wang Z, Yuan X (2014) A strictly contractive Peaceman–Rachford splitting method for convex programming. SIAM J. Optim. 24(3):1011–1040.Crossref, Google Scholar
• Heffley D (1977) Assigning runners to a relay team. Optimal Strategies in Sports, vol. 5 (North Holland, Amsterdam), 169–171.Google Scholar
• Hu H, Sotirov R, Wolkowicz H (2019) Facial reduction for symmetry reduced semidefinite programs. Preprint, submitted February 3, 2022, https://arxiv.org/abs/1912.10245.Google Scholar
• Krarup J, Pruzan P (1978) Computer-aided layout design. Mathematical Programming in Use (Springer, Berlin), 75–94.Crossref, Google Scholar
• Li X, Yuan X (2015) A proximal strictly contractive Peaceman-Rachford splitting method for convex programming with applications to imaging. SIAM J. Imaging Sci. 8(2):1332–1365.Crossref, Google Scholar
• Li X, Pong T, Sun H, Wolkowicz H (2021) A strictly contractive Peaceman-Rachford splitting method for the doubly nonnegative relaxation of the minimum cut problem. Comput. Optim. Appl. 78(3):853–891.Crossref, Google Scholar
• Liu Y, Yuan X, Zeng S, Zhang J (2018) Partial error bound conditions and the linear convergence rate of the alternating direction method of multipliers. SIAM J. Numer. Anal. 56(4):2095–2123.Crossref, Google Scholar
• Mitchell J, Pardalos P, Resende M (1998) Interior point methods for combinatorial optimization. Handbook of Combinatorial Optimization (Springer, Berlin), 189–297.Crossref, Google Scholar
• Monteiro R, Svaiter B (2013) Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers. SIAM J. Optim. 23(1):475–507.Crossref, Google Scholar
• Oliveira D, Wolkowicz H, Xu Y (2018) ADMM for the SDP relaxation of the QAP. Math. Programming Comput. 10(4):631–658.Crossref, Google Scholar
• Pardalos P, Wolkowicz H, eds. (1994) Quadratic Assignment and Related Problems (AMS, Providence, RI).Crossref, Google Scholar
• Pardalos P, Rendl F, Wolkowicz H (1994) The quadratic assignment problem: A survey and recent developments. Pardalos P, Wolkowicz H, eds. Quadratic Assignment and Related Problems (AMS, Providence, RI), 1–42.Crossref, Google Scholar
• Povh J, Rendl F (2009) Copositive and semidefinite relaxations of the quadratic assignment problem. Discrete Optim. 6(3):231–241.Crossref, Google Scholar
• Rendl F, Sotirov R (2007) Bounds for the quadratic assignment problem using the bundle method. Math. Programming 109(2–3, Ser. B):505–524.Crossref, Google Scholar
• Rockafellar R (1997) Convex Analysis. Princeton Landmarks in Mathematics (Princeton University Press, Princeton, NJ).Google Scholar
• Ugi I, Bauer J, Brandt J, Friedrich J, Gasteiger J, Jochum C, Schubert W (1979) Neue anwendungsgebiete für computer in der chemie. Angew. Chem. 91(2):99–111.Crossref, Google Scholar
• van den Berg E, Friedlander M (2008/2009) Probing the Pareto frontier for basis pursuit solutions. SIAM J. Sci. Comput. 31(2):890–912.Crossref, Google Scholar
• von Neumann J (1953) A certain zero-sum two-person game equivalent to the optimal assignment problem. Contributions to the Theory of Games, vol. 2, Annals of Mathematics Studies, no. 28 (Princeton University Press, Princeton, NJ), 5–12.Crossref, Google Scholar
• Wolkowicz H, Saigal R, Vandenberghe L, eds. (2000) Handbook of Semidefinite Programming. International Series in Operations Research & Management Science (Kluwer Academic Publishers, Boston, MA).Crossref, Google Scholar
• Yang L, Sun D, Toh KC (2015) SDPNAL+: A majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints. Math. Programming Comput. 7(3):331–366.Crossref, Google Scholar
• Yang W, Han D (2016) Linear convergence of the alternating direction method of multipliers for a class of convex optimization problems. SIAM J. Numer. Anal. 54(2):625–640.Crossref, Google Scholar
• Yuan X, Zeng S, Zhang J (2020) Discerning the linear convergence of ADMM for structured convex optimization through the lens of variational analysis. J. Machine Learn. Res. 21:1–75.Google Scholar
• Zhao Q, Karisch S, Rendl F, Wolkowicz H (1998) Semidefinite programming relaxations for the quadratic assignment problem. J. Combinatorial Optim. 2(1):71–109.Crossref, Google Scholar