×

zbMATH — the first resource for mathematics

A continuation algorithm for max-cut problem. (English) Zbl 1117.90049
Summary: A continuation algorithm for the solution of max-cut problems is proposed in this paper. Unlike the available semi-definite relaxation, a max-cut problem is converted into a continuous nonlinear programming by employing NCP functions, and the resulting nonlinear programming problem is then solved by using the augmented Lagrange penalty function method. The convergence property of the proposed algorithm is studied. Numerical experiments and comparisons with the Geomeans and Williamson randomized algorithm made on some max-cut test problems show that the algorithm generates satisfactory solutions for all the test problems with much less computation costs.
Reviewer: Reviewer (Berlin)

MSC:
90C06 Large-scale problems in mathematical programming
90C27 Combinatorial optimization
90C30 Nonlinear programming
Software:
CirCut; SDPLR; SDPpack
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Sahni, S., Gonzalez T.: P-complete approximation problem. Journal of ACM, 23, 555–565 (1976) · Zbl 0348.90152 · doi:10.1145/321958.321975
[2] Goemans, M. X., Williamson, D. P.: Improved approximation algorithms for maximum cut and satifiablity problemsusing semidefinite programming. Journal of ACM, 42, 1115–1145 (1995) · Zbl 0885.68088 · doi:10.1145/227683.227684
[3] Anjos, W., Wolkowicz, H.: A strengthened SDP relaxation via a second lifting for the Max Cut problem. Technical Report Research Report CORR 95-55, University of Waterloo, Waterloo, Onratio, 1999 · Zbl 1102.90369
[4] Burer, S., Monteiro, R. D. C., Zhang, Y.: Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs. SIAM Journal on Optimization, 12, 503–521 (2001) · Zbl 1152.90532 · doi:10.1137/S1052623400382467
[5] Xu, D. C., Han, J. Y., Huang, Z. H., Zhang, L.: Improved approximation algorithms for max n/2-directedbisection and max n/2-dense-subgraph. Journal of Global Optimization, 27, 399–410 (2003) · Zbl 1046.90094 · doi:10.1023/A:1026094110647
[6] Xu, D. C., Ye, Y., Zhang, J.: Approximating the 2-catalog segmentation problem using semidefinite programming relaxations. Optimization Methods and Software, 18, 705–719 (2003) · Zbl 1154.90564 · doi:10.1080/10556780310001634082
[7] Huang, Z. H., Han, J. Y., Xu, D. C., Zhang, L.: The non-interior continuation methods for solving the P0-function nonlinear complementarity problem. Science in China, 44, 1107–1114 (2001) · Zbl 1002.90072 · doi:10.1007/BF02877427
[8] Huang, Z. H., Zhang, L., Han, J. Y.: A hybrid smoothing-nonsmooth Newton-type algorithm yielding an exact solution of the P0-LCP. Journal of Computational Mathematics, 22, 797–806 (2004) · Zbl 1068.65075
[9] Liu, H. W., Wang, S. H., Liu, S. Y.: Feasible direction algorithm for solving SDP relaxation of the quadratic {-1, 1} programming. Optimization Methods and Software, 19, 125–136 (2004) · Zbl 1072.65081 · doi:10.1080/10556780410001647203
[10] Burer, S., Monteriro, R. D. C.: A projected gradient algorithm for solving the max-cut relaxation. Optimization Methods and Software, 15, 175–200 (2001) · Zbl 1109.90341 · doi:10.1080/10556780108805818
[11] Burer, S., Monteriro, R. D. C.: A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Mathematical Programming, 95, 329–357 (2003) · Zbl 1030.90077 · doi:10.1007/s10107-002-0352-8
[12] Han, Q. M., Ye, Y., Zhang, J.: An improved rounding method and semidefinite programming relaxation for graph partition. Mathematical Programming, 92, 509–535 (2002) · Zbl 1008.90042 · doi:10.1007/s101070100288
[13] Helmberg, C., Rendle, F.: A spectral bundle method for semidefinite programming. SIAM Journal on Optimization, 10, 673–695 (2000) · Zbl 0960.65074 · doi:10.1137/S1052623497328987
[14] Alizadeh, F., Haeberly, J. P., Overton, M.: Primal dual interior point methods for semidefinite programming: convergence rates, stability and numerical results. SIAM Journal on Optimization, 8, 746–768 (1998) · Zbl 0911.65047 · doi:10.1137/S1052623496304700
[15] Helmberg, C., Rendl, F., Vanderbei, R. J., Wolkowicz, H.; An interior point methods for semidefinite programming. SIAM Jounal on Optimization, 6, 342–361 (1996) · Zbl 0853.65066 · doi:10.1137/0806020
[16] Fischer, A.: A special Newton-type optimization method. Optimization, 24, 269–284 (1992) · Zbl 0814.65063 · doi:10.1080/02331939208843795
[17] Yuan, Y.: Numerical methods for nonlinear programming, Shanghai Scientific & Technical Publishers, Shanghai, 1992
[18] Liu, H. W., Liu, S. Y., Xu, F. M.: A tight semidefinite relaxation of the max cut problem. Journal of Combinatorial Optimization, 7, 237–245 (2003) · Zbl 1175.90335 · doi:10.1023/A:1027364420370
[19] Alizadeh, F., Haeberly, J. P., Nayakkankuppam, M. V., Overton, M. L., Schmieta, S.: SDPpack user’s guide -version 0.9Beta.Technical Report TR1997-737, Courant Institute of Mathematical Science, NYU, New York, NY, June, 1997
[20] Choi, C., Ye, Y.: Solving sparse semidefinite programs using the dual scaling algorithm with an iterative solver, Working paper, Department of Management science, University of Iowa, IA, 2000
[21] Choi, C.: Private communication, University of Iowa, Iowa City, IA, 2000
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.