×

zbMATH — the first resource for mathematics

A computational study of exact subgraph based SDP bounds for max-cut, stable set and coloring. (English) Zbl 1450.90022
Summary: The “exact subgraph” approach was recently introduced as a hierarchical scheme to get increasingly tight semidefinite programming relaxations of several NP-hard graph optimization problems. Solving these relaxations is a computational challenge because of the potentially large number of violated subgraph constraints. We introduce a computational framework for these relaxations designed to cope with these difficulties. We suggest a partial Lagrangian dual, and exploit the fact that its evaluation decomposes into several independent subproblems. This opens the way to use the bundle method from non-smooth optimization to minimize the dual function. Finally computational experiments on the Max-Cut, stable set and coloring problem show the excellent quality of the bounds obtained with this approach.
MSC:
90C22 Semidefinite programming
90C27 Combinatorial optimization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adams, E.; Anjos, MF; Rendl, F.; Wiegele, A., A Hierarchy of subgraph projection-based semidefinite relaxations for some NP-hard graph optimization problems, INFOR Inf. Syst. Oper. Res., 53, 1, 40-47 (2015)
[2] Alizadeh, F., Goldfarb, D.: Second-order cone programming. Math. Program. 95(1, Ser. B), 3-51, iSMP 2000, Part 3. Atlanta, GA (2003) · Zbl 1153.90522
[3] Biq Mac Library: http://biqmac.aau.at/. Last accessed 15 May 2019
[4] Bonnans, JF; Gilbert, JC; Lemaréchal, C.; Sagastizábal, CA, Numerical Optimization: Theoretical and Practical Aspects (2006), Secaucus: Springer, Secaucus
[5] Boros, E.; Crama, Y.; Hammer, PL, Upper-bounds for quadratic \(0-1\) maximization, Oper. Res. Lett., 9, 2, 73-79 (1990) · Zbl 0699.90073
[6] Dash, S.; Puget, JF, On quadratic unconstrained binary optimization problems defined on Chimera graphs, Optima, 98, 2 (2015)
[7] De Santis, M., Rendl, F., Wiegele, A.: Using a Factored Dual in Augmented Lagrangian Methods for Semidefinite Programming. ArXiv e-prints (Oct 2017) · Zbl 07165721
[8] Delorme, C.; Poljak, S., Laplacian eigenvalues and the maximum cut problem, Math. Progr, 62, 3, 557-574 (1993) · Zbl 0797.90107
[9] DIMACS Implementation Challenges: http://dimacs.rutgers.edu/Challenges/ (1992). Last accessed 15 May 2019
[10] Fischer, I.; Gruber, G.; Rendl, F.; Sotirov, R., Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition, Math. Program., 105, 2-3, 451-469 (2006) · Zbl 1085.90044
[11] Frangioni, A.; Gorgone, E., Bundle methods for sum-functions with “easy” components: applications to multicommodity network design, Math. Program., 145, 1, 133-161 (2014) · Zbl 1300.90027
[12] Gaar, E.: Efficient Implementation of SDP Relaxations for the Stable Set Problem. Ph.D. thesis, Alpen-Adria-Universität Klagenfurt (2018)
[13] Gaar, E.; Rendl, F.; Lodi, A.; Nagarajan, V., A bundle approach for SDPs with exact subgraph constraints, Integer Programming and Combinatorial Optimization, 205-218 (2019), Berlin: Springer, Berlin · Zbl 1436.90100
[14] Goemans, MX; Williamson, DP, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. Assoc. Comput. Mach., 42, 6, 1115-1145 (1995) · Zbl 0885.68088
[15] Grötschel, M.; Lovász, L.; Schrijver, A., Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics: Study and Research Texts (1988), Berlin: Springer, Berlin · Zbl 0634.05001
[16] Guruswami, V.; Khanna, S., On the hardness of 4-coloring a 3-colorable graph, SIAM J. Discrete Math., 18, 1, 30-40 (2004) · Zbl 1087.68071
[17] Håstad, J., Clique is hard to approximate within \(n^{1-\epsilon }\), Acta Math., 182, 1, 105-142 (1999) · Zbl 0989.68060
[18] Helmberg, C.; Rendl, F., A spectral bundle method for semidefinite programming, SIAM J. Optim., 10, 3, 673-696 (2000) · Zbl 0960.65074
[19] Hiriart-Urruty, JB; Lemaréchal, C., Convex Analysis and Minimization Algorithms II: Advanced Theory and Bundle Methods (1993), Berlin: Springer, Berlin · Zbl 0795.49002
[20] Khot, S.: Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring. In: 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001), pp. 600-609. IEEE Computer Society, Los Alamitos, CA (2001)
[21] Kiwiel, KC, Proximity control in bundle methods for convex nondifferentiable minimization, Math. Program., 46, 1, 105-122 (1990) · Zbl 0697.90060
[22] Lasserre, J.B.: An explicit exact SDP relaxation for nonlinear 0-1 programs. In: Integer programming and combinatorial optimization (Utrecht, 2001), Lecture Notes in Compututer Science, vol. 2081, pp. 293-303. Springer, Berlin (2001) · Zbl 1010.90515
[23] Laurent, M.; Poljak, S.; Balas, E.; Cornuejols, G.; Kannan, R., The metric polytope, Integer Programming and Combinatorial Optimization, 247-286 (1992), Berlin: Springers, Berlin
[24] Lovász, L., On the shannon capacity of a graph, IEEE Trans. Inf. Theory, 25, 1, 1-7 (1979) · Zbl 0395.94021
[25] 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
[26] MOSEK ApS: The MOSEK optimization toolbox for MATLAB manual. Version 8.0. (2017). http://docs.mosek.com/8.0/toolbox/index.html
[27] Nguyen, T.H., Bui, T.: Graph coloring benchmark instances. https://turing.cs.hbg.psu.edu/txn131/graphcoloring.html. Last accessed 15 May 2019
[28] Rendl, F.; Rinaldi, G.; Wiegele, A., Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations, Math. Program., 121, 2, 307-335 (2010) · Zbl 1184.90118
[29] Rendl, F.; Sotirov, R., Bounds for the quadratic assignment problem using the bundle method, Math. Program., 109, 2-3, 505-524 (2007) · Zbl 1278.90303
[30] Robinson, SM, Bundle-based decomposition: conditions for convergence, Ann. l’I.H.P. Anal. non linéaire, S6, 435-447 (1989) · Zbl 0675.90068
[31] Rockafellar, RT, Convex Analysis. Princeton Mathematical Series, No. 28 (1970), Princeton: Princeton University Press, Princeton
[32] Sherali, HD; Adams, WP, A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems, SIAM J. Discrete Math., 3, 3, 411-430 (1990) · Zbl 0712.90050
[33] Toh, KC; Todd, MJ; Tütüncü, RH, SDPT3—a MATLAB software package for semidefinite programming, version 1.3. Optim, Methods Softw., 11/12, 1-4, 545-581 (1999) · Zbl 0997.90060
[34] Tütüncü, RH; Toh, KC; Todd, MJ, Solving semidefinite-quadratic-linear programs using SDPT3, Math. Program., 95, 2, 189-217 (2003) · Zbl 1030.90082
[35] Yang, L.; Sun, D.; Toh, KC, \({\rm SDPNAL}+\): a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints, Math. Program. Comput., 7, 3, 331-366 (2015) · Zbl 1321.90085
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.