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.