Title: BiqCrunch: A Semidefinite-Based Solver for Binary Quadratic Problems

Lecturer: KRISLOCK, Nathan (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.