BiqCrunch: a semidefinite branch-and-bound method for solving binary quadratic problems

DOI10.1145/3005345MaRDI QIDQ3133583zbMATH OpenOpenAlexWikidataFDO

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

Publication date 5 February 2018

Published in ACM Transactions on Mathematical Software (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3005345

zbMATH Keywords

semidefinite relaxationsbinary quadratic programmingNP-hard problemsquasi-Newton methodsexact resolution

Mathematics Subject Classification ID

Quadratic programming (90C20) Complexity and performance of numerical algorithms (65Y20) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Semidefinite programming (90C22)

Recommendations

• Improved semidefinite bounding procedure for solving max-cut problems to optimality
• A Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations
• Computational comparison of exact solution methods for 0-1 quadratic programs: recommendations for practitioners
• Faster exact solution of sparse maxcut and QUBO problems
• A branch-and-bound algorithm for solving max-\(k\)-cut problem

Cited in

(24)

• Dantzig-Wolfe reformulations for binary quadratic problems
• A subgradient approach for constrained binary optimization via quantum adiabatic evolution
• Faster exact solution of sparse maxcut and QUBO problems
• An experimental evaluation of semidefinite programming and spectral algorithms for max cut
• Certifying optimality of Bell inequality violations: noncommutative polynomial optimization through semidefinite programming and local optimization
• BiqBin: moving boundaries for NP-hard problems by HPC
• A semidefinite approach for the single row facility layout problem
• \texttt{MADAM}: a parallel exact solver for max-cut based on semidefinite programming and ADMM
• BiqBin: A Parallel Branch-and-bound Solver for Binary Quadratic Problems with Linear Constraints
• An entropy-regularized ADMM for binary quadratic programming
• A new global algorithm for max-cut problem with chordal sparsity
• BiqCrunch
• Mathematical programming models and exact algorithms
• 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{EXPEDIS}: an exact penalty method over discrete sets
• QPLIB: a library of quadratic programming instances
• Mining for diamonds -- matrix generation algorithms for binary quadratically constrained quadratic problems
• BDD-based optimization for the quadratic stable set problem
• A Decomposition Augmented Lagrangian Method for Low-Rank Semidefinite Programming
• Combining discrete ellipsoid-based search and branch-and-cut for binary quadratic programming problems
• Polynomial optimization: tightening RLT-based branch-and-bound schemes with conic constraints
• The Chvátal-Gomory procedure for integer SDPs with applications in combinatorial optimization
• Partial Lasserre relaxation for sparse Max-Cut

Describes a project that uses

Uses Software

• BARON
• LAPACK
• SCIP
• L-BFGS-B
• BOB

This page was built for publication: BiqCrunch: a semidefinite branch-and-bound method for solving binary quadratic problems

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