BiqCrunch
BiqCrunch is a semidefinite-based solver for binary quadratic problems. It uses a branch-and-bound method featuring an improved semidefinite bounding procedure [4], mixed with a polyhedral approach (see [2,3] for details). BiqCrunch uses a particular BC input file format that is similar to the SDPA format to describe the combinatorial problems. We provide also a LP to BC conversion tool . Documentation is available here.
The second release (May 2016) of BiqCrunch is now available as a free and open-source software. Specific versions are provided for solving Max-Cut, k-cluster and Max-independent set problems, as well as conversion tools for these problems. You can also use BiqCrunch online to solve any 0-1 quadratic problem to optimality, or simply to get an SDP-quality bound [4].
Papers
- [1] N. Krislock, J. Malick, F. Roupin. BiqCrunch : a semidefinite branch-and-bound method for solving binary quadratic problems. ACM Transactions on Mathematical Software 43(4), 2017.
-
[2] N. Krislock, J. Malick, F. Roupin.
Computational results of a semidefinite branch-and-bound algorithm for k-cluster. Computers and Operations Research 66: 153–159, 2016.
-
[3] N. Krislock, J. Malick, F. Roupin:
Improved semidefinite bounding procedure for solving Max-Cut problems to optimality. Mathematical Programming A 143(1/2): 61-86, 2014.
-
[4] J. Malick, F. Roupin:
On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds for 0-1 quadratic problems leading to quasi-Newton methods. Mathematical Programming B (140)1 pp 99-124, 2013.
Acknowledgments
BiqCrunch is the outcome of several research works and collaborations. This work was supported by the LIPN lab, CNRS (through “GdR Recherche Opérationnelle”), Grenoble University (Université Joseph Fourier, through “Pôle Math-STIC”). We thank: Quentin Monnet and Lise-Marie Veillon (students of ENSIIE, Evry, France in 2008) for their help in developing and testing parts of a preliminary version of the solver, and Geoffrey Kozak (student of Sup Galilée, Villetaneuse, France in 2012) for his help in developing several tools and for testing the solver.
This website was created by Marco Casazza. Please feel free to contact F. Roupin with any questions or suggestions.