Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations

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

zbMATH Keywords

cut polytope unconstrained binary quadratic optimization

Mathematics Subject Classification ID

Semidefinite programming (90C22) Quadratic programming (90C20) Combinatorial optimization (90C27)

Related Items

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