Improved semidefinite bounding procedure for solving max-cut problems to optimality

DOI10.1007/s10107-012-0594-zzbMath1285.90030OpenAlexW2069154666MaRDI QIDQ2436651

Jérôme Malick, Nathan Krislock, Frédéric Roupin

Publication date: 25 February 2014

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-012-0594-z

zbMATH Keywords

semidefinite programmingcombinatorial optimizationtriangle inequalitiesquasi-Newton algorithm

Mathematics Subject Classification ID

Semidefinite programming (90C22) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Related Items

BiqBin: A Parallel Branch-and-bound Solver for Binary Quadratic Problems with Linear Constraints, The Boolean Quadric Polytope, Mathematical Programming Models and Exact Algorithms, Computational results of a semidefinite branch-and-bound algorithm for \(k\)-cluster, Computational study of valid inequalities for the maximum \(k\)-cut problem, On the solution of nonconvex cardinality Boolean quadratic programming problems: a computational study, Computational study of a branching algorithm for the maximum \(k\)-cut problem, Partial Lasserre relaxation for sparse Max-Cut, On solving a large-scale problem on facility location and customer assignment with interaction costs along a time horizon, Semidefinite Approaches for MIQCP: Convex Relaxations and Practical Methods, An entropy-regularized ADMM for binary quadratic programming, A new global algorithm for max-cut problem with chordal sparsity, Continuous Approaches to the Unconstrained Binary Quadratic Problems, Solving SDP relaxations of max-cut problem with large number of hypermetric inequalities by L-BFGS-B, A matrix nonconvex relaxation approach to unconstrained binary polynomial programs, An Exact Algorithm for the Quadratic Multiknapsack Problem with an Application to Event Seating, \texttt{MADAM}: a parallel exact solver for max-cut based on semidefinite programming and ADMM, A branch-and-bound algorithm for solving max-\(k\)-cut problem, Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints, Theoretical and computational study of several linearisation techniques for binary quadratic problems, Linear size MIP formulation of max-cut: new properties, links with cycle inequalities and computational results, Discrete Optimization with Decision Diagrams, From Graph Orientation to the Unweighted Maximum Cut, Exact Solution Methods for the k-Item Quadratic Knapsack Problem, Global convergence of the alternating projection method for the Max-Cut relaxation problem

Uses Software

• LAPACK
• L-BFGS-B
• L-BFGS
• LBFGS-B
• Biq Mac
• BiqMac
• BOB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computational results of a semidefinite branch-and-bound algorithm for \(k\)-cluster
• On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds for 0--1 quadratic problems leading to quasi-Newton methods
• Reflections on generating (disjunctive) cuts
• Handbook on semidefinite, conic and polynomial optimization
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem
• The spherical constraint in Boolean quadratic programs
• Quadratic programming with one negative eigenvalue is NP-hard
• Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
• Convex analysis and nonlinear optimization. Theory and examples
• A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
• Gap inequalities for the cut polytope
• Solving \(k\)-cluster problems to optimality with semidefinite programming
• Computational aspects of a branch and bound algorithm for quadratic zero- one programming
• Introduction to Semidefinite, Conic and Polynomial Optimization
• Computational Approaches to Max-Cut
• Remark on “algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound constrained optimization”
• LAPACK Users' Guide
• Algorithm 778: L-BFGS-B
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• A Limited Memory Algorithm for Bound Constrained Optimization
• Reducibility among Combinatorial Problems
• Numerical optimization. Theoretical and practical aspects. Transl. from the French
• Benchmarking optimization software with performance profiles.