×

zbMATH — the first resource for mathematics

Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations. (English) Zbl 1184.90118
Summary: We present a method for finding exact solutions of Max-Cut, the problem of finding a cut of maximum weight in a weighted graph. We use a Branch-and-Bound setting that applies a dynamic version of the bundle method as bounding procedure. This approach uses Lagrangian duality to obtain a “nearly optimal” solution of the basic semidefinite Max-Cut relaxation, strengthened by triangle inequalities. The expensive part of our bounding procedure is solving the basic semidefinite relaxation of the Max-Cut problem, which has to be done several times during the bounding process. We review other solution approaches and compare the numerical results with our method. We also extend our experiments to instances of unconstrained quadratic 0-1 optimization and to instances of the graph equipartition problem. The experiments show that our method nearly always outperforms all other approaches. In particular, for dense graphs, where linear programming-based methods fail, our method performs very well. Exact solutions are obtained in a reasonable time for any instance of size up to \(n = 100\), independent of the density. For some problems of special structure, we can solve even larger problem classes. We could prove optimality for several problems of the literature where, to the best of our knowledge, no other method is able to do so.

MSC:
90C20 Quadratic programming
90C22 Semidefinite programming
90C27 Combinatorial optimization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achterberg, T.: Constraint integer programming. PhD thesis, Technische Universität Berlin. http://opus.kobv.de/tuberlin/volltexte/2007/1611/ (2007) · Zbl 1171.90476
[2] Achterberg T., Koch T., Martin A.: Branching rules revisited. Oper. Res. Lett. 33(1), 42–54 (2005) · Zbl 1076.90037 · doi:10.1016/j.orl.2004.04.002
[3] Armbruster, M.: Branch-and-Cut for a semidefinite relaxation of the minimum bisection problem. PhD thesis, University of Technology Chemnitz (2007)
[4] Barahona F., Ladányi L.: Branch and cut based on the volume algorithm: Steiner trees in graphs and max-cut. RAIRO Oper. Res. 40(1), 53–73 (2006) · Zbl 1146.90090 · doi:10.1051/ro:2006010
[5] Barahona F., Mahjoub A.R.: On the cut polytope. Math. Program. 36(2), 157–173 (1986) · Zbl 0616.90058 · doi:10.1007/BF02592023
[6] Barahona F., Jünger M., Reinelt G.: Experiments in quadratic 0–1 programming. Math. Program. 44(2, (Ser. A)), 127–137 (1989) · Zbl 0677.90046 · doi:10.1007/BF01587084
[7] Beasley J.E.: Or-library: distributing test problems by electronic mail. J. Oper. Res. Soc. 41(11), 1069–1072 (1990)
[8] Beasley, J.E.: Or-library. http://people.brunel.ac.uk/\(\sim\)mastjjb/jeb/info.html (1990)
[9] Beasley, J.E.: Heuristic algorithms for the unconstrained binary quadratic programming problem. Technical report, The Management School, Imperial College, London SW7 2AZ, England (1998)
[10] Benson, S.J., Ye, Y., Zhang, X.: Solving large-scale sparse semidefinite programs for combinatorial optimization. SIAM J. Optim. 10(2), 443–461 (2000, electronic) · Zbl 0997.90059
[11] Billionnet A., Elloumi S.: Using a mixed integer quadratic programming solver for the unconstrained quadratic 0–1 problem. Math. Program. 109(1, Ser. A), 55–68 (2007) · Zbl 1278.90263 · doi:10.1007/s10107-005-0637-9
[12] Boros, E., Hammer, P.L., Tavares, G.: The pseudo-boolean optimization. http://rutcor.rutgers.edu/\(\sim\)pbo/ (2005)
[13] Boros E., Hammer P.L., Sun R., Tavares G.: A max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO). Discrete Optim. 5(2), 501–529 (2008) · Zbl 1170.90454 · doi:10.1016/j.disopt.2007.02.001
[14] Burer, S., Monteiro, R.D., Zhang, Y.: Rank-two relaxation heuristics for max-cut and other binary quadratic programs. SIAM J. Optim. 12(2), 503–521 (2001/2002, electronic) · Zbl 1152.90532
[15] De Simone C., Diehl M., Jünger M., Mutzel P., Reinelt G., Rinaldi G.: Exact ground states of Ising spin glasses: new experimental results with a branch-and-cut algorithm. J. Stat. Phys. 80(1–2), 487–496 (1995) · Zbl 1106.82323 · doi:10.1007/BF02178370
[16] Delorme C., Poljak S.: Laplacian eigenvalues and the maximum cut problem. Math. Program. 62(3, Ser. A), 557–574 (1993) · Zbl 0797.90107 · doi:10.1007/BF01585184
[17] Deza M.M., Laurent M.: Geometry of Cuts and Metrics. In: Algorithms and Combinatorics, vol. 15. Springer, Berlin (1997) · Zbl 0885.52001
[18] Elf, M., Gutwenger, C., Jünger, M., Rinaldi, G.: Branch-and-Cut Algorithms for Combinatorial Optimization and Their Implementation in ABACUS. In: Lecture Notes in Computer Science, vol. 2241, pp. 157–222. Springer, Heidelberg (2001) · Zbl 1052.90106
[19] 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, Ser. B), 451–469 (2006) · Zbl 1085.90044 · doi:10.1007/s10107-005-0661-9
[20] Frangioni A., Lodi A., Rinaldi G.: New approaches for optimizing over the semimetric polytope. Math. Program. 104(2–3, Ser. B), 375–388 (2005) · Zbl 1124.90043 · doi:10.1007/s10107-005-0620-5
[21] Glover F., Kochenberger G., Alidaee B.: Adaptative memory tabu search for binary quadratic programs. Manage. Sci. 44(3), 336–345 (1998) · Zbl 0989.90072 · doi:10.1287/mnsc.44.3.336
[22] Goemans, M.X., Williamson, D.P.: .878-approximation algorithms for max cut and max 2sat. In: Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pp. 422–431. Montreal, Quebec, Canada (1994) · Zbl 1345.68274
[23] Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. Assoc. Comput. Mach. 42(6), 1115–1145 (1995, preliminary version see [22] · Zbl 0885.68088
[24] Hansen P.: Methods of nonlinear 0–1 programming. Ann. Discrete Math. 5, 53–70 (1979) · Zbl 0426.90063 · doi:10.1016/S0167-5060(08)70343-1
[25] Helmberg, C.: Fixing variables in semidefinite relaxations. SIAM J. Matrix Anal. Appl. 21(3), 952–969 (2000, electronic) · Zbl 0961.90075
[26] Helmberg, C.: A cutting plane algorithm for large scale semidefinite relaxations. In: The Sharpest Cut, MPS/SIAM Ser. Optim., pp. 233–256. SIAM, Philadelphia, PA (2004) · Zbl 1136.90431
[27] Helmberg C., Rendl F.: Solving quadratic (0,1)-problems by semidefinite programs and cutting planes. Math. Program. 82(3, Ser. A), 291–315 (1998) · Zbl 0919.90112
[28] Helmberg C., Rendl F., Vanderbei R.J., Wolkowicz H.: An interior-point method for semidefinite programming. SIAM J. Optim. 6(2), 342–361 (1996) · Zbl 0853.65066 · doi:10.1137/0806020
[29] Johnson D.S., Aragon C.R., McGeoch L.A., Schevon C.: Optimization by simulated annealing: an experimental evaluation. part i, graph partitioning. Oper. Res. 37(6), 865–892 (1989) · Zbl 0698.90065 · doi:10.1287/opre.37.6.865
[30] Jünger, M., Reinelt, G., Rinaldi, G.: Lifting and separation procedures for the cut polytope. Technical report, Universität zu Köln (2006, in preparation) · Zbl 1297.90133
[31] Karisch, S.E., Rendl, F.: Semidefinite programming and graph equipartition. In: Topics in semidefinite and interior-point methods (Toronto, ON, 1996). In: Fields Inst. Commun., vol. 18, pp. 77–95. American Mathematical Society, Providence (1998) · Zbl 0905.90171
[32] Kim S., Kojima M.: Second order cone programming relaxation of nonconvex quadratic optimization problems. Optim. Methods Softw. 15(3-4), 201–224 (2001) · Zbl 1109.90327 · doi:10.1080/10556780108805819
[33] Laurent M.: The max-cut problem. In: Dell’Amico, M., Maffioli, F., Martello, S.(eds) Annotated Bibliographies in Combinatorial Optimization, pp. 241–259. Wiley, Chichester (1997) · Zbl 1068.90517
[34] Liers, F.: Contributions to determining exact ground-states of Ising spin-glasses and to their physics. PhD thesis, Universität zu Köln (2004)
[35] Liers F., Jünger M., Reinelt G., Rinaldi G.: Computing exact ground states of hard Ising spin glass problems by branch-and-cut. In: Hartmann, A., Rieger, H.(eds) New Optimization Algorithms in Physics, pp. 47–68. Wiley, London (2004) · Zbl 1059.90147
[36] Muramatsu M., Suzuki T.: A new second-order cone programming relaxation for MAX-CUT problems. J. Oper. Res. Soc. Jpn 46(2), 164–177 (2003) · Zbl 1109.90337
[37] Pardalos P.M., Rodgers G.P.: Computational aspects of a branch and bound algorithm for quadratic zero-one programming. Computing 45(2), 131–144 (1990) · Zbl 0721.65034 · doi:10.1007/BF02247879
[38] Pardalos P.M., Rodgers G.P.: Parallel branch and bound algorithms for quadratic zero-one programs on the hypercube architecture. Ann. Oper. Res. 22(1–4), 271–292 (1990) · Zbl 0722.90047 · doi:10.1007/BF02023057
[39] Poljak S., Rendl F.: Solving the max-cut problem using eigenvalues. Discrete Appl. Math. 62(1–3), 249–278 (1995) · Zbl 0838.90131 · doi:10.1016/0166-218X(94)00155-7
[40] Poljak S., Rendl F.: Nonpolyhedral relaxations of graph-bisection problems. SIAM J. Optim. 5(3), 467–487 (1995) · Zbl 0838.90130 · doi:10.1137/0805024
[41] Rendl F.: Semidefinite programming and combinatorial optimization. Appl. Numer. Math. 29(3), 255–281 (1999) · Zbl 0956.90030 · doi:10.1016/S0168-9274(98)00097-X
[42] Rendl, F., Rinaldi, G., Wiegele, A.: A branch and bound algorithm for Max-Cut based on combining semidefinite and polyhedral relaxations. In: Integer programming and combinatorial optimization. Lecture Notes in Computer Science, vol. 4513, pp. 295–309. Springer, Berlin (2007) · Zbl 1136.90461
[43] Rinaldi, G.: Rudy. http://www-user.tu-chemnitz.de/\(\sim\)helmberg/rudy.tar.gz (1998)
[44] Wiegele, A.: Nonlinear optimization techniques applied to combinatorial optimization problems. PhD thesis, Alpen-Adria-Universität Klagenfurt (2006)
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.