BiqCrunch: a semidefinite branch-and-bound method for solving binary quadratic problems
DOI10.1145/3005345zbMATH Open1380.90284OpenAlexW2562729437WikidataQ113310149 ScholiaQ113310149MaRDI QIDQ3133583FDOQ3133583
Nathan Krislock, Frédéric Roupin, Jérôme Malick
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
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
semidefinite relaxationsbinary quadratic programmingNP-hard problemsquasi-Newton methodsexact resolution
Quadratic programming (90C20) Complexity and performance of numerical algorithms (65Y20) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Semidefinite programming (90C22)
Cited In (22)
- QPLIB: a library of quadratic programming instances
- A subgradient approach for constrained binary optimization via quantum adiabatic evolution
- \texttt{MADAM}: a parallel exact solver for max-cut based on semidefinite programming and ADMM
- An experimental evaluation of semidefinite programming and spectral algorithms for max cut
- Dantzig-Wolfe reformulations for binary quadratic problems
- Partial Lasserre relaxation for sparse Max-Cut
- A semidefinite approach for the single row facility layout problem
- Mining for diamonds -- matrix generation algorithms for binary quadratically constrained quadratic problems
- BiqCrunch
- An entropy-regularized ADMM for binary quadratic programming
- A Decomposition Augmented Lagrangian Method for Low-Rank Semidefinite Programming
- \texttt{EXPEDIS}: an exact penalty method over discrete sets
- Mathematical Programming Models and Exact Algorithms
- Faster exact solution of sparse maxcut and QUBO problems
- Certifying optimality of Bell inequality violations: noncommutative polynomial optimization through semidefinite programming and local optimization
- BDD-based optimization for the quadratic stable set problem
- BiqBin: A Parallel Branch-and-bound Solver for Binary Quadratic Problems with Linear Constraints
- A new global algorithm for max-cut problem with chordal sparsity
- 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
- A matrix nonconvex relaxation approach to unconstrained binary polynomial programs
- An Exact Algorithm for the Quadratic Multiknapsack Problem with an Application to Event Seating
Uses Software
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)
