Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem. (English) Zbl 1184.90120
Summary: We consider semidefinite programming relaxations of the quadratic assignment problem, and show how to exploit group symmetry in the problem data. Thus, we are able to compute the best known lower bounds for several instances of quadratic assignment problems from the problem library in [R. E. Burkard et al., J. Glob. Optim. 10, No. 4, 391–403 (1997; Zbl 0884.90116)].
MSC:
| 90C22 | Semidefinite programming |
| 70-08 | Computational methods for problems pertaining to mechanics of particles and systems |
Citations:
Zbl 0884.90116References:
| [1] | Anstreicher K.M.: Recent advances in the solution of quadratic assignment problems. Math. Program. Ser. B 97, 27–42 (2003) · Zbl 1035.90067 |
| [2] | Anstreicher K.M., Brixius N., Linderoth J., Goux J.-P.: Solving large quadratic assignment problems on computational grids. Math. Program. Ser. B 91, 563–588 (2002) · Zbl 1030.90105 · doi:10.1007/s101070100255 |
| [3] | Borchers B.: CSDP, a C library for semidefinite programming. Optim. Meth. Softw. 11/12(1–4), 613–623 (1999) · Zbl 0973.90524 · doi:10.1080/10556789908805765 |
| [4] | Burer S., Vandenbussche D.: Solving lift-and-project relaxations of binary integer programs. SIAM J. Optim. 16, 726–750 (2006) · Zbl 1113.90100 · doi:10.1137/040609574 |
| [5] | Eschermann, B., Wunderlich, H.J.: Optimized synthesis of self-testable finite state machines. In: 20th International Symposium on Fault-tolerant Computing (FFTCS 20), Newcastle upon Tyne, 26–28 June 1990 |
| [6] | Burkard, R.E., Karisch, S.E., Rendl, F.: QAPLIB–a quadratic assignment problem library. J. Global Optim. 10, 291–403 (1997); see also http://www.seas.upenn.edu/qaplib/ · Zbl 0884.90116 |
| [7] | Klerk E., Maharry J., Pasechnik D.V., Richter B., Salazar G.: Improved bounds for the crossing numbers of K m,n and K n . SIAM J. Discr. Math. 20, 189–202 (2006) · Zbl 1111.05029 · doi:10.1137/S0895480104442741 |
| [8] | Klerk E., Pasechnik D.V., Schrijver A.: Reduction of symmetric semidefinite programs using the regular *-representation. Math. Program. B 109(2–3), 613–624 (2007) · Zbl 1200.90136 · doi:10.1007/s10107-006-0039-7 |
| [9] | de Klerk, E., Pasechnik, D.V., Sotirov, R.: On semidefinite programming relaxations of the traveling salesman problem. CentER discussion paper 2007-101, Tilburg University, The Netherlands (2007). Available at: http://arno.uvt.nl/show.cgi?fid=67481 |
| [10] | GAP–groups, algorithms, and programming, Version 4.4.9, The GAP group (2006) http://www.gap-system.org |
| [11] | Gatermann K., Parrilo P.A.: Symmetry groups, semidefinite programs, and sum of squares. J. Pure Appl. Algebra 192, 95–128 (2004) · Zbl 1108.13021 · doi:10.1016/j.jpaa.2003.12.011 |
| [12] | Gijswijt, D.: Matrix algebras and semidefinite programming techniques for codes. PhD Thesis, University of Amsterdam, The Netherlands (2005). http://staff.science.uva.nl/\(\sim\)gijswijt/promotie/thesis.pdf · Zbl 1113.90101 |
| [13] | Gilmore P.C.: Optimal and suboptimal algorithms for the quadratic assignment problem. SIAM J. Appl. Math. 10, 305–31 (1962) · Zbl 0118.15101 · doi:10.1137/0110022 |
| [14] | Graham A.: Kronecker products and matrix calculus with applications. Ellis Horwood Limited, Chichester (1981) · Zbl 0497.26005 |
| [15] | Grone R., Johnson C.R., Sá E.M., Wolkowicz H.: Positive definite completions of partial Hermitian matrices. Lin. Algebra Appl. 58, 109–124 (1984) · Zbl 0547.15011 · doi:10.1016/0024-3795(84)90207-6 |
| [16] | Lawler E.: The quadratic assignment problem. Manage. Sci. 9, 586–599 (1963) · Zbl 0995.90579 · doi:10.1287/mnsc.9.4.586 |
| [17] | Lovász L., Schrijver A.: Cones of matrices and set-functions and 0–1 optimization. SIAM J. Optim. 1(2), 166–190 (1991) · Zbl 0754.90039 · doi:10.1137/0801013 |
| [18] | Peng, J., Mittelmann, H., Wu, X.: Graph modeling for quadratic assignment problem associated with the hypercube. Technical report, Department of IESE, UIUC, Urbana, IL, 61801, USA (2007). Available at Optimization Online |
| [19] | Povh, J., Rendl, F.: Copositive and semidefinite relaxations of the quadratic assignment problem. Manuscript (2006). http://www.optimization-online.org/DB_HTML/2006/10/1502.html · Zbl 1167.90597 |
| [20] | Rendl F., Sotirov R.: Bounds for the quadratic assignment problem using the bundle method. Math Program Ser B 109(2–3), 505–524 (2007) · Zbl 1278.90303 · doi:10.1007/s10107-006-0038-8 |
| [21] | Schrijver A.: A comparison of the Delsarte and Lovász bounds. IEEE Trans. Inf. Theory 25, 425–429 (1979) · Zbl 0444.94009 · doi:10.1109/TIT.1979.1056072 |
| [22] | Schrijver A.: New code upper bounds from the Terwilliger algebra. IEEE Trans Inf Theory 51, 2859–2866 (2005) · Zbl 1298.94152 · doi:10.1109/TIT.2005.851748 |
| [23] | Serre J.-P.: Linear representations of finite groups. Graduate texts in mathematics, vol. 42. Springer, New York (1977) |
| [24] | Sturm J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Meth. Softw. 11–12, 625–653 (1999) · Zbl 0973.90526 · doi:10.1080/10556789908805766 |
| [25] | Wedderburn J.H.M.: On hypercomplex numbers. Proc. Lond. Math. Soc. 6(2), 77–118 (1907) · JFM 38.0135.02 · doi:10.1112/plms/s2-6.1.77 |
| [26] | Wedderburn, J.H.M.: Lectures on matrices. AMS Colloquium Publications, vol. 17. AMS publishers (1934) · Zbl 0010.09904 |
| [27] | Löfberg, J.: YALMIP : A toolbox for modeling and optimization in MATLAB. In: Proceedings of the CACSD conference, Taipei, Taiwan (2004). http://control.ee.ethz.ch/\(\sim\)joloef/yalmip.php |
| [28] | Zhao Q., Karisch S.E., Rendl F., Wolkowicz H.: Semidefinite programming relaxations for the quadratic assignment problem. J. Combin. Optim. 2, 71–109 (1998) · Zbl 0904.90145 · doi:10.1023/A:1009795911987 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
