Skip to main content
Seminar | Mathematics and Computer Science Division

BiqCrunch: Solving Binary Quadratic Problems Efficiently Using Semidefinite Optimization

LANS Informal Seminar

Abstract: 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.

This seminar will be streamed