BiqBin: A Parallel Branch-and-bound Solver for Binary Quadratic Problems with Linear Constraints

DOI10.1145/3514039OpenAlexW3085548870WikidataQ113309844 ScholiaQ113309844MaRDI QIDQ5883708

Angelika Wiegele, Janez Povh, Borut Lužar, Nicolò Gusmeroli, Timotej Hrga, Melanie Siebenhofer

Publication date: 22 March 2023

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

Full work available at URL: https://arxiv.org/abs/2009.06240

zbMATH Keywords

semidefinite programmingparallel algorithmsbinary quadratic programmingsolvers

Mathematics Subject Classification ID

Numerical analysis (65-XX)

Related Items

Faster exact solution of sparse maxcut and QUBO problems, Solving SDP relaxations of max-cut problem with large number of hypermetric inequalities by L-BFGS-B, BiqBin

Uses Software

• SCIP
• MIPLIB
• CPLEX
• Gurobi
• Biq Mac
• ISLR
• BiqMac
• Rudy
• BiqCrunch
• QPLIB
• MADAM

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parallel branch and bound algorithms for quadratic zero-one programs on the hypercube architecture
• 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 quadratic knapsack problem -- a survey
• Experiments in quadratic 0-1 programming
• Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
• A MAX-CUT formulation of 0/1 programs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Applications of cut polyhedra. II
• QPLIB: a library of quadratic programming instances
• On the solution of nonconvex cardinality Boolean quadratic programming problems: a computational study
• Improved semidefinite bounding procedure for solving max-cut problems to optimality
• Metaheuristic clustering
• A review on algorithms for maximum clique problems
• Computational aspects of a branch and bound algorithm for quadratic zero- one programming
• \texttt{EXPEDIS}: an exact penalty method over discrete sets
• BiqCrunch
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• An Introduction to Statistical Learning
• Reducibility among Combinatorial Problems
• A Survey on Parallel Computing and its Applications in Data-Parallel Problems Using GPU Architectures
• Different Formulations for Solving the HeaviestK-Subgraph Problem