BiqCrunch: A Semidefinite Branch-and-Bound Method for Solving Binary Quadratic Problems

Nathan Krislock, Jérôme Malick, Frédéric RoupinACM Trans. Math. Softw 2017 · OpenReview

Abstract

This article presents BiqCrunch, an exact solver for binary quadratic optimization problems. BiqCrunch is a branch-and-bound method that uses an original, efficient semidefinite-optimization-based bounding procedure. It has been successfully tested on a variety of well-known combinatorial optimization problems, such as Max-Cut, Max-k-Cluster, and Max-Independent-Set. The code is publicly available online; a web interface and many conversion tools are also provided.
BibTeX
@article{krislock2017biqcrunch,
  author = {Nathan Krislock and Jérôme Malick and Frédéric Roupin},
  title = {{BiqCrunch: A Semidefinite Branch-and-Bound Method for Solving Binary Quadratic Problems}},
  journal = {ACM Trans. Math. Softw.},
  year = {2017},
  url = {https://openreview.net/forum?id=PfuMDxDPwq4},
}

Loading related content...

Figure