Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
From MaRDI portal
Publication:847837
DOI10.1007/S10107-008-0235-8zbMath1184.90118OpenAlexW2033498477WikidataQ58002887 ScholiaQ58002887MaRDI QIDQ847837
Angelika Wiegele, Giovanni Rinaldi, Franz Rendl
Publication date: 19 February 2010
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-008-0235-8
Related Items (95)
An Improved Interior-Point Cutting-Plane Method for Binary Quadratic Optimization ⋮ BiqBin: A Parallel Branch-and-bound Solver for Binary Quadratic Problems with Linear Constraints ⋮ On handling cutting planes in interior-point methods for solving semi-definite relaxations of binary quadratic optimization problems ⋮ Dantzig-Wolfe reformulations for binary quadratic problems ⋮ Matrix Relaxations in Combinatorial Optimization ⋮ The Boolean Quadric Polytope ⋮ Mathematical Programming Models and Exact Algorithms ⋮ QUBO Software ⋮ Global optimization advances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO ⋮ Memetic search for the max-bisection problem ⋮ Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem ⋮ LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison ⋮ Computational study of valid inequalities for the maximum \(k\)-cut problem ⋮ On the solution of nonconvex cardinality Boolean quadratic programming problems: a computational study ⋮ A computational study and survey of methods for the single-row facility layout problem ⋮ On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds for 0--1 quadratic problems leading to quasi-Newton methods ⋮ Semidefinite relaxations for non-convex quadratic mixed-integer programming ⋮ SpeeDP: an algorithm to compute SDP bounds for very large max-cut instances ⋮ Solving \(k\)-cluster problems to optimality with semidefinite programming ⋮ A class of spectral bounds for max \(k\)-cut ⋮ Generalised 2-circulant inequalities for the max-cut problem ⋮ \texttt{EXPEDIS}: an exact penalty method over discrete sets ⋮ Computational study of a branching algorithm for the maximum \(k\)-cut problem ⋮ A note on the 2-circulant inequalities for the MAX-cut problem ⋮ Partial Lasserre relaxation for sparse Max-Cut ⋮ Quantum Annealing versus Digital Computing ⋮ A new approximation hierarchy for polynomial conic optimization ⋮ Lifting and separation procedures for the cut polytope ⋮ Semidefinite Approaches for MIQCP: Convex Relaxations and Practical Methods ⋮ An entropy-regularized ADMM for binary quadratic programming ⋮ Faster exact solution of sparse maxcut and QUBO problems ⋮ A semidefinite optimization approach to the target visitation problem ⋮ A new global algorithm for max-cut problem with chordal sparsity ⋮ New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph ⋮ On some edge Folkman numbers, small and large ⋮ Approximate Counting with Deterministic Guarantees for Affinity Computation ⋮ Optimal design of line replaceable units ⋮ A computational study of exact subgraph based SDP bounds for max-cut, stable set and coloring ⋮ Solving SDP relaxations of max-cut problem with large number of hypermetric inequalities by L-BFGS-B ⋮ An exact algorithm for graph partitioning ⋮ A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for Some NP-Hard Graph Optimization Problems ⋮ A quadratic simplex algorithm for primal optimization over zero-one polytopes ⋮ Linear programing relaxations for a strategic pricing problem in electricity markets ⋮ BiqBin: Moving Boundaries for NP-hard Problems by HPC ⋮ A matrix nonconvex relaxation approach to unconstrained binary polynomial programs ⋮ Certifiably optimal sparse inverse covariance estimation ⋮ Improved semidefinite bounding procedure for solving max-cut problems to optimality ⋮ On global optimization with indefinite quadratics ⋮ A semidefinite relaxation based global algorithm for two-level graph partition problem ⋮ Cuts in undirected graphs. I ⋮ Cuts in undirected graphs. II ⋮ Optimal price zones of electricity markets: a mixed-integer multilevel model and global solution approaches ⋮ What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO ⋮ Computational protein design as an optimization problem ⋮ \texttt{MADAM}: a parallel exact solver for max-cut based on semidefinite programming and ADMM ⋮ A multilevel analysis of the Lasserre hierarchy ⋮ A branch-and-bound algorithm for solving max-\(k\)-cut problem ⋮ Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem ⋮ Unifying semidefinite and set-copositive relaxations of binary problems and randomization techniques ⋮ A framework for solving mixed-integer semidefinite programs ⋮ A Lagrangian decomposition approach to computing feasible solutions for quadratic binary programs ⋮ Local search inequalities ⋮ Gaussian mean field lattice gas ⋮ Maximum-entropy sampling and the Boolean quadric polytope ⋮ Improving spectral bounds for clustering problems by Lagrangian relaxation ⋮ Improving a Lagrangian decomposition for the unconstrained binary quadratic programming problem ⋮ Solving a cut problem in bipartite graphs by linear programming: application to a forest management problem ⋮ Successive Lagrangian relaxation algorithm for nonconvex quadratic optimization ⋮ Extensions on ellipsoid bounds for quadratic integer programming ⋮ QPLIB: a library of quadratic programming instances ⋮ Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints ⋮ Semidefinite relaxations for partitioning, assignment and ordering problems ⋮ Theoretical and computational study of several linearisation techniques for binary quadratic problems ⋮ Computational Approaches to Max-Cut ⋮ Linear size MIP formulation of max-cut: new properties, links with cycle inequalities and computational results ⋮ Discrete Optimization with Decision Diagrams ⋮ Semidefinite relaxations for partitioning, assignment and ordering problems ⋮ Faster, but weaker, relaxations for quadratically constrained quadratic programs ⋮ Volume computation for sparse Boolean quadric relaxations ⋮ A branch-and-cut algorithm for solving mixed-integer semidefinite optimization problems ⋮ An exact combinatorial algorithm for minimum graph bisection ⋮ From Graph Orientation to the Unweighted Maximum Cut ⋮ Set-completely-positive representations and cuts for the max-cut polytope and the unit modulus lifting ⋮ Biq Mac ⋮ Greedy differencing edge-contraction heuristic for the max-cut problem ⋮ Relaxing Nonconvex Quadratic Functions by Multiple Adaptive Diagonal Perturbations ⋮ On linear conic relaxation of discrete quadratic programs ⋮ Exact Solution Methods for the k-Item Quadratic Knapsack Problem ⋮ A Novel SDP Relaxation for the Quadratic Assignment Problem Using Cut Pseudo Bases ⋮ Spectral bounds for graph partitioning with prescribed partition sizes ⋮ An Active-Set Method for Second-Order Conic-Constrained Quadratic Programming ⋮ Engineering Branch-and-Cut Algorithms for the Equicut Problem ⋮ Global convergence of the alternating projection method for the Max-Cut relaxation problem ⋮ Convex optimization under combinatorial sparsity constraints ⋮ A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lifting and separation procedures for the cut polytope
- SCIP: solving constraint integer programs
- Parallel branch and bound algorithms for quadratic zero-one programs on the hypercube architecture
- Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem
- A Max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO)
- Experiments in quadratic 0-1 programming
- Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
- Laplacian eigenvalues and the maximum cut problem
- Branching rules revisited
- Solving the max-cut problem using eigenvalues
- Exact ground states of Ising spin glasses: new experimental results with a branch-and-cut algorithm
- New approaches for optimizing over the semimetric polytope
- Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition
- Computational aspects of a branch and bound algorithm for quadratic zero- one programming
- Second order cone programming relaxation of nonconvex quadratic optimization problems
- Adaptive Memory Tabu Search for Binary Quadratic Programs
- Rank-Two Relaxation Heuristics for MAX-CUT and Other Binary Quadratic Programs
- .879-approximation algorithms for MAX CUT and MAX 2SAT
- Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut
- Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
- Methods of Nonlinear 0-1 Programming
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- A NEW SECOND-ORDER CONE PROGRAMMING RELAXATION FOR MAX-CUT PROBLEMS
- On the cut polytope
- Nonpolyhedral Relaxations of Graph-Bisection Problems
- An Interior-Point Method for Semidefinite Programming
- Fixing Variables in Semidefinite Relaxations
- Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization
- A Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations
- Semidefinite programming and combinatorial optimization
- Geometry of cuts and metrics
This page was built for publication: Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
