×

zbMATH — the first resource for mathematics

A discrete filled function algorithm for approximate global solutions of max-cut problems. (English) Zbl 1148.65041
There have been very few attempts in using the filled function methods to solve max-cut or other combinatorial optimization problem. The max-cut problem can be expressed as a discrete quadratic optimization problem. This paper proposes a discrete filled function algorithm to find approximate global solutions for NP-hard max-cut problems. The proposed algorithm is implemented by a two-phase cycle. In the first phase, a local minimizer is obtained by using the 1-neighborhood local search in the objective function of the discrete quadratic optimization problem. In the second phase, the discrete filled function from some neighbor points of the local optimizer is minimized. The two cycles are iterated until the stopping conditions are met. Some numerical experimental results are presented.

MSC:
65K05 Numerical mathematical programming methods
90C20 Quadratic programming
90C27 Combinatorial optimization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] F. Alizadeh, J. Haeberly, M. Nayakkankuppam, M. Overton, S. Schmieta, SDPPACK use’s guide: version 0.9 beta for MATLAB5.0, 1997.
[2] Alperin, H.; Nowak, I., Lagrangian smoothing heuristics for MAX-cut, J. heuristics, 11, 447-463, (2005) · Zbl 1122.90426
[3] Barahona, F.; Grötschel; Reinelt, G., An application of combinatorial optimization to statistical physics and circuit layout design, Oper. res., 36, 493-513, (1988) · Zbl 0646.90084
[4] Bertsimas, D.; Ye, Y., Semidefinite relaxations, multivariate normal distributions, and order statistics, (), 1-17 · Zbl 1052.90594
[5] Burer, S.; Monteiro, R.D.C., A projected gradient algorithm for solving the maxcut SDP relaxation, Optimization methods and software, 15, 175-200, (2001) · Zbl 1109.90341
[6] Burer, S.; Monteiro, R.D.C.; Zhang, Y., Rank-two relaxation heuristics for MAX-cut and other binary quadratic programs, SIAM J. optim., 12, 503-521, (2001) · Zbl 1152.90532
[7] Festa, P.; Pardalos, P.M.; Resende, M.G.C.; Ribeiro, C.C., Randomized heuristics for the MAX-cut problem, Optimization methods and software, 17, 1033-1058, (2002) · Zbl 1032.90073
[8] Garey, M.; Johnson, D.; Stochmeter, L., Some simplified NP-complete graph problems, Theoret. comput. sci., 1, 237-267, (1976) · Zbl 0338.05120
[9] Ge, R.-P., A filled function method for finding a global minimizer of a function of several variables, Math. programming, 46, 191-204, (1990) · Zbl 0694.90083
[10] Ge, R.-P.; Huang, C.B., A continuous approach to nonlinear integer programming, Appl. math. comput., 34, 1, 39-60, (1989) · Zbl 0682.90067
[11] 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) · Zbl 0885.68088
[12] Gu, Y.H.; Wu, Z.Y., A new filled function method for nonlinear integer programming problem, Appl. math. comput., 173, 938-950, (2006) · Zbl 1091.65055
[13] X.-L. He, C.-X. Xu, C.-C. Zhu, A new class of filled functions for global minimization, computation intelligence and security, part I, in: Proceedings Lecture Notes in Artificial Intelligence, vol. 3801, 2005, pp. 1088-1093.
[14] Karp, R.M., Reducibility among combinatorial problems, (), 85-103 · Zbl 0366.68041
[15] Liu, X., Finding global minima with a computable filled function, J. global optim., 19, 151-161, (2001) · Zbl 1033.90088
[16] Ng, C.-K.; Zhang, L.-S.; Li, D.; Tian, W.-W., Discrete filled function method for discrete global optimization, Comput. optim. appl., 31, 87-115, (2005) · Zbl 1114.90125
[17] Shang, Y.-L.; Zhang, L.-S., A filled function method for finding a global minimizer on global integer optimization, J. comput. appl. math., 181, 200-210, (2005) · Zbl 1078.65054
[18] Xu, C.-X.; He, X.-L.; Xu, F.-M., An effective continuous algorithm for approximate solutions of large scale MAX-cut problems, J. comput. math., 24, 6, 749-760, (2006) · Zbl 1133.65034
[19] Xu, F.-M.; Xu, C.-X.; Xue, H.-G., A feasible direction algorithm without line search for solving MAX-bisection problem, J. comput. math., 23, 619-634, (2005) · Zbl 1086.65062
[20] Xu, Z.; Huang, H.-X.; Pardalos, P.M.; Xu, C.X., Filled functions for unconstrained global optimization, J. global optim., 20, 49-65, (2001) · Zbl 1049.90092
[21] Zhang, L.-S.; Ng, C.; Li, D.; Tian, W.-W., A new filled function method for global optimization, J. global optim., 28, 17-43, (2004) · Zbl 1061.90109
[22] Zhu, W.-X., An approximate algorithm for nonlinear integer programming, Appl. math. comput., 93, 2-3, 183-193, (1998) · Zbl 0938.90052
[23] U. Zwick, Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems, in: Proceedings of 31st STOC, 1999, pp. 679-687. · Zbl 1345.90064
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.