Lagrangian smoothing heuristics for Max-cut

DOI10.1007/s10732-005-3603-zzbMath1122.90426OpenAlexW2119186543MaRDI QIDQ2491324

Hernán Alperin, Ivo Nowak

Publication date: 29 May 2006

Published in: Journal of Heuristics (Search for Journal in Brave)

Full work available at URL: http://edoc.hu-berlin.de/18452/3271

zbMATH Keywords

quadratic programmingsemidefinite programmingcombinatorial optimizationnon-convex programmingpathfollowingapproximation methods and heuristics

Mathematics Subject Classification ID

Semidefinite programming (90C22) Nonconvex programming, global optimization (90C26) Quadratic programming (90C20) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (8)

An augmented Lagrangian method for binary quadratic programming based on a class of continuous functions ⋮ A new discrete filled function method for solving large scale max-cut problems ⋮ Global optimality conditions and optimization methods for quadratic integer programming problems ⋮ A discrete filled function algorithm for approximate global solutions of max-cut problems ⋮ A polynomial case of convex integer quadratic programming problems with box integer constraints ⋮ A discrete dynamic convexized method for the max-cut problem ⋮ An efficient Lagrangian smoothing heuristic for max-cut ⋮ A filled function method for quadratic programs with binary constraints†

Uses Software

• LaGO
• SeDuMi
• ARPACK
• SDPLR
• CirCut
• COL
• DIMACS
• NOA
• Outward rotations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Proximity control in bundle methods for convex nondifferentiable minimization
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• Rank-Two Relaxation Heuristics for MAX-CUT and Other Binary Quadratic Programs
• Outward rotations
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Randomized heuristics for the Max-Cut problem
• A Spectral Bundle Method for Semidefinite Programming
• Dual Applications of Proximal Bundle Methods, Including Lagrangian Relaxation of Nonconvex Problems
• Pathfollowing methods in nonlinear optimization III: Lagrange multiplier embedding
• Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization

This page was built for publication: Lagrangian smoothing heuristics for Max-cut