A SEMI-DEFINITE RELAXATION BRANCH-AND-BOUND ALGORITHM FOR BINARY INTEGER QUADRATIC PROBLEMS USING SCIPSUITE

Abstract

The Binary Quadratic Optimization Problem is a classical problem and studied in many fields. Typical applications include the 0-1 Quadratic Problem (QP), the Maximum Cut Problem (MAXCUT), k-Cluster Problem (kCluster), Maximum Independent Set Problem (MIS) as well as the Exact k-Quadratic Knapsack Problems (EkQKP). This thesis focuses on a branch-and-bound algorithm using the SCIP-SDP framework, a leading non-commercial branch-and-bound software using the SDPA solver to solve the semidefinite programming relaxation problem of each node. However, SDPA is severely limited by its capacity to solve large problems efficiently.

We consider a symmetric Gauss-Seidel Alternating Direction Method of Multipliers (sGS-ADMM) solver as an alternative to better handle large problems. To speed up computation, we utilized sparse data structures and other heuristics to better handle large datasets. Our experimental results demonstrate that sGS-ADMM provides improved efficiency for large datasets. Under additional constraints, sGS-ADMM is also able to attain better results for smaller problems.