Abstract
We present an improved algorithm for finding exact solutions to Max-Cut and the related binary quadratic programming problem, both classic problems of combinatorial optimization. The algorithm uses a branch-(and-cut-)and-bound paradigm, using standard valid inequalities and nonstandard semidefinite bounds. More specifically, we add a quadratic regularization term to the strengthened semidefinite relaxation in order to use a quasi-Newton method to compute the bounds. The ratio of the tightness of the bounds to the time required to compute them depends on two real parameters; we show how adjusting these parameters and the set of strengthening inequalities gives us a very efficient bounding procedure. Embedding our bounding procedure in a generic branch-and-bound platform, we get a competitive algorithm: extensive experiments show that our algorithm dominates the best existing method.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Anderson, E., Bai, Z., Bischof, C., Blackford, S., Demmel, J., Dongarra, J., Du Croz, J., Greenbaum, A., Hammarling, S., McKenney, A., Sorensen, D.: LAPACK Users’ Guide, 3rd edn. Society for Industrial and Applied Mathematics, Philadelphia (1999)
Anjos, M.F., Lasserre, J.B. (eds.): Handbook on Semidefinite, Conic and Polynomial Optimization, International Series in Operations Research & Management Science, vol.166. Springer, USA (2012)
Anjos, M.F., Lasserre, J.B.: Introduction to semidefinite, conic and polynomial optimization. In: Anjos, M.F., Lasserre, J.B (eds.) Handbook on Semidefinite, Conic and Polynomial Optimization, International Series in Operations Research & Management Science, vol.166, pp. 1–22. Springer, USA (2012)
Billionnet, A., Elloumi, S.: Using a mixed integer quadratic programming solver for the unconstrained quadratic 0–1 problem. Math. Program. 109, 55–68 (2007)
Bonnans, J., Gilbert, J., Lemaréchal, C., Sagastizábal, C.: Numerical Optimization. Springer, Berlin (2003)
Borwein, J.M., Lewis, A.S.: Convex Analysis and Nonlinear Optimization: Theory and Examples. Springer, Berlin (2000)
Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2008)
Byrd, R.H., Lu, P., Nocedal, J., Zhu, C.: A limited memory algorithm for bound constrained optimization. SIAM J. Sci. Comput. 16(5), 1190–1208 (1995)
Cadoux, F., Lemaréchal, C.: Reflections on generating (disjunctive) cuts. EURO J. Comput. Optim. (Submitted, 2012)
Cun, B.L., Roucairol, C., The PNN Team: BOB: A Unified Platform for Implementing Branch-and-Bound Like Algorithms. Technical Report 95/16, University of Versailles Saint-Quentin-en-Yvelines (1995).
Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002)
Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6), 1115–1145 (1995)
Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore (1996)
Helmberg, C., Rendl, F.: Solving quadratic (0,1)-problems by semidefinite programs and cutting planes. Math. Program. 82, 291–315 (1998)
Hiriart-Urruty, J.B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms. Springer, Heidelberg (Two volumes) (1993)
Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations (Proceedings of Symposium, IBM Thomas J. Watson Res. Center, Yorktown Heights, NY, 1972), pp. 85–103. Plenum, New York (1972)
Krislock, N., Malick, J., Roupin, F.: Improved semidefinite branch-and-bound algorithm for \(k\)-cluster (Submitted, 2012). Available online as preprint hal-00717212
Laurent, M., Poljak, S.: Gap inequalities for the cut polytope. Eur. J. Comb. 17(2–3), 233–254 (1996)
Lemaréchal, C., Oustry, F.: Semidefinite Relaxations and Lagrangian Duality with Application to Combinatorial Optimization. Rapport de Recherche 3710, INRIA (1999)
Malick, J.: Spherical constraint in Boolean quadratic programming. J. Glob. Optim. 39(4) (2007)
Malick, J., Roupin, F.: On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds leading to Newton-like methods. Math. Program. B (to appear, 2012). Available online as preprint hal-00662367
Malick, J., Roupin, F.: Solving k-cluster problems to optimality using adjustable semidefinite programming bounds. Math. Program. B Special Issue Mixed Integer Nonlinear Program (to appear, 2012)
Morales, J.L., Nocedal, J.: Remark on “Algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound constrained optimization”. ACM Trans. Math. Softw. 38(1), 1–4 (2011)
Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer, Berlin (2006)
Palagi, L., Piccialli, V., Rendl, F., Rinaldi, G., Wiegele, A.: Computational approaches to Max-Cut. In: Anjos, M.F., Lasserre, J.B. (eds.) Handbook on Semidefinite, Conic and Polynomial Optimization, International Series in Operations Research& Management Science, vol.166, pp. 821–847. Springer, USA (2012)
Pardalos, P., Rodgers, G.: Computational aspects of a branch and bound algorithm for quadratic zero-one programming. Computing 45, 134–144 (1990)
Pardalos, P.M., Vavasis, S.A.: Quadratic programming with one negative eigenvalue is NP-hard. J. Glob. Optim. 1, 15–22 (1991)
Poljak, S., Rendl, F., Wolkowicz, H.: A recipe for semidefinite relaxation for (0,1)-quadratic programming. J. Glob. Optim. 7, 51–73 (1995)
Rendl, F., Rinaldi, G., Wiegele, A.: Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxations. Math. Program. 121, 307–335 (2010)
Wiegele, A.: Nonlinear Optimization Techniques Applied to Combinatorial Optimization Problems. Ph.D. thesis, Alpen-Adria-Universität Klagenfurt (2006)
Wiegele, A.: Biq Mac Library–A collection of Max-Cut and quadratic 0–1 programming instances of medium size. Technical report, Alpen-Adria-Universität Klagenfurt, Klagenfurt, Austria (2007)
Zhu, C., Byrd, R.H., Lu, P., Nocedal, J.: Algorithm 778: L-BFGS-B: fortran subroutines for large-scale bound-constrained optimization. ACM Trans. Math. Softw. 23(4), 550–560 (1997)
Acknowledgments
We are grateful to Angelika Wiegele for the discussions we have had and for providing us with a copy of the Biq Mac solver for our numerical comparison.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Krislock, N., Malick, J. & Roupin, F. Improved semidefinite bounding procedure for solving Max-Cut problems to optimality. Math. Program. 143, 61–86 (2014). https://doi.org/10.1007/s10107-012-0594-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-012-0594-z