Rank-Two Relaxation Heuristics for MAX-CUT and Other Binary Quadratic Programs
From MaRDI portal
Publication:2784422
DOI10.1137/S1052623400382467zbMath1152.90532OpenAlexW2051598459MaRDI QIDQ2784422
Renato D. C. Monteiro, Samuel Burer, Yin Zhang
Publication date: 23 April 2002
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s1052623400382467
semidefinite relaxationbinary quadratic programscontinuous optimization heuristicsMAX-CUT and MAX-BISECTIONrank-two relaxation
Large-scale problems in mathematical programming (90C06) Nonlinear programming (90C30) Combinatorial optimization (90C27)
Related Items (46)
Feasible direction algorithm for solving the SDP relaxations of quadratic {−1, 1} programming problems ⋮ An augmented Lagrangian method for binary quadratic programming based on a class of continuous functions ⋮ Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations ⋮ On computational capabilities of Ising machines based on nonlinear oscillators ⋮ Probabilistic GRASP-tabu search algorithms for the UBQP problem ⋮ A continuation algorithm for max-cut problem ⋮ An effective iterated tabu search for the maximum bisection problem ⋮ Memetic search for the max-bisection problem ⋮ A nonmonotone GRASP ⋮ Semidefinite representations for finite varieties ⋮ Solving maximum-entropy sampling problems using factored masks ⋮ Teams of global equilibrium search algorithms for solving the weighted maximum cut problem in parallel ⋮ Solving combinatorial optimisation problems using oscillator based Ising machines ⋮ Faster exact solution of sparse maxcut and QUBO problems ⋮ A new global algorithm for max-cut problem with chordal sparsity ⋮ An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem ⋮ Max-Cut via Kuramoto-Type Oscillators ⋮ A quadratic simplex algorithm for primal optimization over zero-one polytopes ⋮ A matrix nonconvex relaxation approach to unconstrained binary polynomial programs ⋮ A new discrete filled function method for solving large scale max-cut problems ⋮ Linear and quadratic programming approaches for the general graph partitioning problem ⋮ Global optimality conditions and optimization methods for quadratic integer programming problems ⋮ Solving the maxcut problem by the global equilibrium search ⋮ On a polynomial fractional formulation for independence number of a graph ⋮ An improved linearization strategy for zero-one quadratic programming problems ⋮ Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem ⋮ A discrete filled function algorithm for approximate global solutions of max-cut problems ⋮ A Max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO) ⋮ Constructing test functions for global optimization using continuous formulations of graph problems ⋮ A multiple search operator heuristic for the max-k-cut problem ⋮ Hybridizing the cross-entropy method: An application to the max-cut problem ⋮ Path relinking for unconstrained binary quadratic programming ⋮ A discrete dynamic convexized method for the max-cut problem ⋮ An efficient Lagrangian smoothing heuristic for max-cut ⋮ Lagrangian smoothing heuristics for Max-cut ⋮ Randomized heuristics for the Max-Cut problem ⋮ Benign landscapes of low-dimensional relaxations for orthogonal synchronization on general graphs ⋮ A filled function method for quadratic programs with binary constraints† ⋮ Cheeger's cut, maxcut and the spectral theory of 1-Laplacian on graphs ⋮ A discrete filled function algorithm embedded with continuous approximation for solving max-cut problems ⋮ CirCut ⋮ A CONTINUATION APPROACH USING NCP FUNCTION FOR SOLVING MAX-CUT PROBLEM ⋮ A global continuation algorithm for solving binary quadratic programming problems ⋮ Nonconvex Phase Synchronization ⋮ Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition ⋮ A continuation approach for solving binary quadratic program based on a class of NCP-functions
This page was built for publication: Rank-Two Relaxation Heuristics for MAX-CUT and Other Binary Quadratic Programs
