A new discrete filled function method for solving large scale max-cut problems

DOI10.1007/S11075-011-9522-1MaRDI QIDQ438797zbMATH OpenOpenAlexFDO

Authors Ai-Fan Ling, Cheng-Xian Xu

Publication date 31 July 2012

Published in Numerical Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11075-011-9522-1

zbMATH Keywords

combinatorial optimizationglobal optimizationnumerical experimentsundirected graphmax-cut problemfilled function

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Nonconvex programming, global optimization (90C26)

Recommendations

• A discrete filled function algorithm for approximate global solutions of max-cut problems
• A discrete filled function algorithm embedded with continuous approximation for solving max-cut problems
• Discrete filled function method for discrete global optimization
• A discrete dynamic convexized method for the max-cut problem
• Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem

Cites work

• scientific article; zbMATH DE number 1302192 (Why is no real title available?)
• scientific article; zbMATH DE number 5232308 (Why is no real title available?)
• scientific article; zbMATH DE number 3390827 (Why is no real title available?)
• A Spectral Bundle Method for Semidefinite Programming
• A continuous approach to nonlinear integer programming
• A filled function method for finding a global minimizer of a function of several variables
• A filled function method for finding a global minimizer on global integer optimization
• A new filled function method for global optimization
• A new filled function method for nonlinear integer programming problem
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• An approximate algorithm for nonlinear integer programming
• Discrete filled function method for discrete global optimization
• Filled functions for unconstrained global optimization.
• Finding global minima with a computable filled function.
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Lagrangian smoothing heuristics for Max-cut
• Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems
• Randomized heuristics for the Max-Cut problem
• Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs
• Some simplified NP-complete graph problems

Cited in

(6)

• A discrete filled function algorithm for approximate global solutions of max-cut problems
• Non parameter-filled function for global optimization
• Solving the maxcut problem by the global equilibrium search
• A discrete dynamic convexized method for the max-cut problem
• Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem
• A discrete filled function algorithm embedded with continuous approximation for solving max-cut problems

Describes a project that uses

Uses Software

• Outward rotations
• CirCut
• SDPpack
• Matlab

This page was built for publication: A new discrete filled function method for solving large scale max-cut problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q438797)