Copositivity cuts for improving SDP bounds on the clique number. (English) Zbl 1198.90312
Summary: Adding cuts based on copositive matrices, we propose to improve Lovász’ bound \(\theta \) on the clique number and its tightening \(\theta ^{\prime}\) introduced by McEliece, Rodemich, Rumsey, and Schrijver. Candidates for cheap and efficient copositivity cuts of this type are obtained from graphs with known clique number. The cost of previously established semidefinite programming bound hierarchies starting with \(\theta ^{\prime}\) rapidly increases with the order (and quality requirements). By contrast, the bounds proposed here are relatively cheap in the sense that computational effort is comparable to that required for \(\theta ^{\prime}\).
MSC:
| 90C20 | Quadratic programming |
| 90C22 | Semidefinite programming |
| 90C27 | Combinatorial optimization |
| 90C35 | Programming involving graphs or networks |
References:
| [1] | Bomze I.M.: Copositive optimization. In: Floudas, C.A., Pardalos, P.M. (eds) Encyclopedia of Optimization, pp. 561–564. Springer, New York (2009) |
| [2] | Bomze I.M., Budinich M., Pardalos P., Pelillo M.: The maximum clique problem. In: Du, D.-Z., Pardalos, P.M. (eds) Handbook of Combinatorial Optimization (supp., vol. A), pp. 1–74. Kluwer, Dordrecht (1999) · Zbl 1253.90188 |
| [3] | Bomze, I.M., Frommlet, F., Locatelli, M.: Gap, cosum, and product properties of the {\(\theta\)}’ bound on the clique number. To appear in Optimization (2010) · Zbl 1214.05102 |
| [4] | Bomze I.M., Locatelli M., Tardella F.: New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability. Math. Program. 115, 31–64 (2008) · Zbl 1171.90007 · doi:10.1007/s10107-007-0138-0 |
| [5] | Borchers B.: CSDP, a C library for semidefinite programming. Optim. Methods Softw. 11, 613–623 (1999) · Zbl 0973.90524 · doi:10.1080/10556789908805765 |
| [6] | Burer S.: On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120, 479–495 (2009) · Zbl 1180.90234 · doi:10.1007/s10107-008-0223-z |
| [7] | Busygin S.: Copositive programming. In: Floudas, C.A., Pardalos, P.M. (eds) Encyclopedia of Optimization (2nd edn), pp. 564–567. Springer, New York (2009) |
| [8] | de Klerk E., Pasechnik D.V.: Approximation of the stability number of a graph via copositive programsming. SIAM J. Optim. 12, 875–892 (2002) · Zbl 1035.90058 · doi:10.1137/S1052623401383248 |
| [9] | Dukanović I., Rendl F.: Semidefinite programming relaxations for graph coloring and maximal clique problems. Math. Program. B 109, 345–365 (2007) · Zbl 1278.90299 · doi:10.1007/s10107-006-0026-z |
| [10] | Gvozdenović, N., Laurent, M.: Semidefinite bounds for the stability number of a graph via sums of squares of polynomials. In: Lecture Notes in Computer Science, vol. 3509, 136–151. Springer, New York (2005) · Zbl 1119.05323 |
| [11] | Knuth D.E.: The sandwich theorem. Electron. J. Comb. 22, 1–48 (1994) · Zbl 0810.05065 |
| [12] | Lasserre J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11, 796–817 (2001) · Zbl 1010.90061 · doi:10.1137/S1052623400366802 |
| [13] | Lasserre, J.B.: An explicit exact SDP relaxation for nonlinear 0-1 programming. In: Aardal K., Gerards A.H.M. (eds.) Lecture Notes in Computer Science, vol. 2081, 293–303. Springer, New York (2001) · Zbl 1010.90515 |
| [14] | Loefberg, J.: YALMIP : A Toolbox for Modeling and Optimization in MATLAB. In: Proceedings of the CACSD Conference, Taipei, Taiwan (2004) |
| [15] | Lovász L.: On the Shannon capacity of a graph. IEEE Trans. Inf. Theory 25, 1–7 (1979) · Zbl 0395.94021 · doi:10.1109/TIT.1979.1055985 |
| [16] | McEliece R.J., Rodemich E.R., Rumsey H.C.: The Lovász’ bound and some generalizations. J. Comb. Inf. Syst. Sci. 3, 134–152 (1978) · Zbl 0408.05031 |
| [17] | Peña J., Vera J., Zuluaga L.: Computing the stability number of a graph via linear and semidefinite programming. SIAM J. Optim. 18, 87–105 (2007) · Zbl 1176.90611 |
| [18] | Schrijver A.: A comparison of the Delsarte and Lovasz bounds. IEEE Trans. Inf. Theory 25, 425–429 (1979) · Zbl 0444.94009 · doi:10.1109/TIT.1979.1056072 |
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.
