Alperin, Hernán; Nowak, Ivo Lagrangian smoothing heuristics for Max-cut. (English) Zbl 1122.90426 J. Heuristics 11, No. 5-6, 447-463 (2005). Summary: This paper presents a smoothing heuristic for an NP-hard combinatorial problem. Starting with a convex Lagrangian relaxation, a pathfollowing method is applied to obtain good solutions while gradually transforming the relaxed problem into the original problem formulated with an exact penalty function. Starting points are drawn using different sampling techniques that use randomization and eigenvectors. The dual point that defines the convex relaxation is computed via eigenvalue optimization using subgradient techniques.The proposed method turns out to be competitive with the most recent ones. The idea presented here is generic and can be generalized to all box-constrained problems where convex Lagrangian relaxation can be applied. Furthermore, to the best of our knowledge, this is the first time that a Lagrangian heuristic is combined with pathfollowing techniques. Cited in 8 Documents MSC: 90C59 Approximation methods and heuristics in mathematical programming 90C27 Combinatorial optimization 90C22 Semidefinite programming 90C26 Nonconvex programming, global optimization 90C20 Quadratic programming Keywords:semidefinite programming; quadratic programming; combinatorial optimization; non-convex programming; approximation methods and heuristics; pathfollowing Software:SDPLR; COL; SeDuMi; CirCut; Outward rotations; ARPACK; NOA; LaGO; DIMACS PDFBibTeX XMLCite \textit{H. Alperin} and \textit{I. Nowak}, J. Heuristics 11, No. 5--6, 447--463 (2005; Zbl 1122.90426) Full Text: DOI Link References: [1] Beasley, J.E. (1998). ”Heuristic Algorithms for the Unconstrained Binary Quadratic Programming Problem.” Tech. Rep., The Management School, Imperial College, London SW7 2AZ, England, http://mscmga.ms.ic.ac.uk/jeb/jeb.html. [2] Benson, S.J., Y. Ye, and X. Zhang. (2000). ”Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization.” SIAM J. Optim. 10(2), 443–461. · Zbl 0997.90059 [3] Berloni, A., P. Campadelli, and G. Grossi. (1998). ”An Approximation Algorithm for the Maximum Cut Problem and its Experimental Analysis,” In Proceedings of ”Algorithms and Experiments”, pp. 137–143. [4] Bertsekas, D.P. (1995). Non-Linear Programming. Belmont, MA: Athena Scientific. · Zbl 0935.90037 [5] Bertsimas, D. and Y. Ye. (1998). ”Semidefinite Relaxations, Multivariate Normal Distributions, and Order Statistics.” In D.-Z. Du and P. Pardalos, (eds.), Handbook of Combinatorial Optimization, Kluwer Academic Publishers, pp. 1–19. · Zbl 1052.90594 [6] Burer, S., R.D.C. Monteiro, and Y. Zhang. (2001). ”Rank-two Relaxation Heuristics for Max-cut and Other Binary Quadratic Programs.” SIAM J.Opt. 12, 503–521. · Zbl 1152.90532 [7] Burer, S. and R.M. Monteiro. (2003). ”A Nonlinear Programming Algorithm for Solving Semidefinite Programs via Low-rank Factorization.” Mathematical Programming (Series B) 95, 329–357. · Zbl 1030.90077 [8] Dentcheva, D., J. Guddat, and J.-J. Rückmann. (1995). Pathfollowing Methods in Nonlinear Optimization III: Multiplier Embedding.” ZOR - Math. Methods of OR 41, 127–152. · Zbl 0854.90127 [9] Feltenmark, S. and K.C. Kiwiel. (2000). ”Dual Applications of Proximal Bundle Methods Including Lagrangian Eelaxation of Nonconvex Problems.” SIAM J. Optim. 10(3), 697–721. · Zbl 0958.65070 [10] Festa, P., P.M. Pardalos, M.G.C. Resende, and C.C. Ribeiro. (2002). ”Randomized Heuristics for the Max-cut Problem.” Optimization Methods and Software 7, 1033–1058. · Zbl 1032.90073 [11] Garey, M.R. and D.S. Johnson. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. · Zbl 0411.68039 [12] Gomes, F. and D. Sorensen. (1997). ARPACK++: a C++ Implementation of ARPACK Eigenvalue Package. http://www.crpc.rice.edu/software/ARPACK/. [13] Goemans, M.X. and D.P. Williamson. (1995). ”Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming.” J. ACM 42, 1115–1145. · Zbl 0885.68088 [14] Guddat, J., F. Guerra, and D. Nowack. (1998). ”On the Role of the Mangasarian-Fromovitz Constraints Qualification for Penalty-, Exact Penalty- and Lagrange Multiplier Methods.” In A.V. Fiacco (ed.), Mathematical Programming with Data Perturbations. New York: Marcel Deckker, Inc., pp. 159–183. · Zbl 0888.90136 [15] Guddat, J., F.G. Vazquez, and H.T. Jongen. (1990). Parametric Optimization: Singularities, Pathfollowing and Jumps. John Wiley and Sons. · Zbl 0718.90056 [16] Helmberg, C. (2000). ”Semidefinite Programming for Combinatorial Optimization.” Tech. Rep., ZIB-Report 00–34. [17] Helmberg, C. and F. Rendl. (2000). ”A Spectral Bundle Method for Semidefinite Programming.” SIAM J. Opt. 10(3), 673–695. · Zbl 0960.65074 [18] Hiriart-Urruty, J.B. and C. Lemaréchal. (1993). Convex Analysis and Minimization Algorithms I and II, Berlin: Springer. · Zbl 0795.49001 [19] Kiwiel, K.C. (1990). ”Proximity Control in Bundle Methods for Convex Nondifferentiable Minimization.” Math. Progr. 46, 105–122. · Zbl 0697.90060 [20] Kiwiel, K.C. (1993/1994). User’s Guide for NOA 2.0/3.0: A FORTRAN Package for Convex Nondifferentiable Optimization. Warsaw: Polish Academy of Science, System Research Institute. [21] Nowak, I. (2002). ”Lagrangian Decomposition of Mixed-Integer All-Quadratic Programs.” Tech. Rep., HU-Berlin NR-2002–7. [22] Nowak, I. (2004). ”Relaxation and Decomposition Methods for Mixed Integer Nonlinear Programming.” Habilitation thesis, Humboldt Universität zu Berlin, Institut für Mathematik, Rudower Chaussee 25, D-10099 Berlin. [23] Pataki, G. and S.H. Schmieta. (2000). The DIMACS Library of Mixed Semidefinite Quadratic Linear Programs, http://dimacs.rutgers.edu/Challenges/Seventh/Instances/. [24] Schelstraete, S., W. Schepens, and H. Verschelde. (1998). ”Energy Minimization by Smoothing Techniques: A Survey.” In E.P. Balbuena and J. Seminario, (eds.), From Classical to Quantum Methods, Elsevier, pp. 129–185. [25] Warners, J.P. (1999). ”Nonlinear Approaches to Satisfiability Problems.” PhD thesis, Eindhoven University of Technology. · Zbl 0944.68073 [26] Zwick, U. (1999). ”Outward Rotations: A Tool for Rounding Solutions of Semidefinite Programming Relaxations, with Applications to Max cut and Other Problems.” In Proc. of 31th STOC, 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.