BiqCrunch: Solving Binary Quadratic Problems Efficiently Using Semidefinite Optimization

Nathan Krislock
Seminar

BiqCrunch is a branch-and-bound solver using semidefinite optimization to compute high-quality bounds for binary quadratic problems, such as MaxCut, Max-k-Cluster, Maximum-Independent-Set, Exact Quadratic Knapsack, and the Quadratic Assignment Problem. BiqCrunch does not use an interior-point method for computing its bounds. Instead, an eigenvalue solver and a gradient-based method are used to compute tight bounds. We will discuss our bounding procedure and give an update on the new features and performance enhancements of the latest version of BiqCrunch.