Groupe d’études et de recherche en analyse des décisions

BiqCrunch: A Semidefinite-Based Solver for Binary Quadratic Problems

Nathan Krislock Northern Illinois University, États-Unis

BiqCrunch is a new branch-and-bound solver for finding exact solutions of any 0-1 quadratic problem, such as Max-Cut, Max-\(k\)-cluster, and Max-independent set. The bounds are based on a regularized semidefinite relaxation and are efficiently computable using eigenvalue decomposition and a quasi-Newton optimization method. The resulting semidefinite bounding procedure gives us a competitive branch-and-bound algorithm for solving many such combinatorial optimization problems to optimality.