BiqCrunch: a semidefinite branch-and-bound method for solving binary quadratic problems. 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.
Keywords for this software
References in zbMATH (referenced in 9 articles , 1 standard article )
Showing results 1 to 9 of 9.
- Ceselli, Alberto; Létocart, Lucas; Traversi, Emiliano: Dantzig-Wolfe reformulations for binary quadratic problems (2022)
- Hrga, Timotej; Lužar, Borut; Povh, Janez; Wiegele, Angelika: BiqBin: moving boundaries for NP-hard problems by HPC (2021)
- Hrga, Timotej; Povh, Janez: \textttMADAM: a parallel exact solver for max-cut based on semidefinite programming and ADMM (2021)
- Bergman, David: An exact algorithm for the quadratic multiknapsack problem with an application to event seating (2019)
- Furini, Fabio; Traversi, Emiliano; Belotti, Pietro; Frangioni, Antonio; Gleixner, Ambros; Gould, Nick; Liberti, Leo; Lodi, Andrea; Misener, Ruth; Mittelmann, Hans; Sahinidis, Nikolaos V.; Vigerske, Stefan; Wiegele, Angelika: QPLIB: a library of quadratic programming instances (2019)
- Buchheim, Christoph; Traversi, Emiliano: Quadratic combinatorial optimization using separable underestimators (2018)
- Garraffa, Michele; Della Croce, Federico; Salassa, Fabio: An exact semidefinite programming approach for the max-mean dispersion problem (2017)
- Karimi, Sahar; Ronagh, Pooya: A subgradient approach for constrained binary optimization via quantum adiabatic evolution (2017)
- Krislock, Nathan; Malick, Jérôme; Roupin, Frédéric: BiqCrunch: a semidefinite branch-and-bound method for solving binary quadratic problems (2017)