BiqCrunch

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

Anything in here will be replaced on browsers that support the canvas element

References in zbMATH (referenced in 9 articles , 1 standard article )

Showing results 1 to 9 of 9.
Sorted by year (citations)

  1. Ceselli, Alberto; Létocart, Lucas; Traversi, Emiliano: Dantzig-Wolfe reformulations for binary quadratic problems (2022)
  2. Hrga, Timotej; Lužar, Borut; Povh, Janez; Wiegele, Angelika: BiqBin: moving boundaries for NP-hard problems by HPC (2021)
  3. Hrga, Timotej; Povh, Janez: \textttMADAM: a parallel exact solver for max-cut based on semidefinite programming and ADMM (2021)
  4. Bergman, David: An exact algorithm for the quadratic multiknapsack problem with an application to event seating (2019)
  5. 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)
  6. Buchheim, Christoph; Traversi, Emiliano: Quadratic combinatorial optimization using separable underestimators (2018)
  7. Garraffa, Michele; Della Croce, Federico; Salassa, Fabio: An exact semidefinite programming approach for the max-mean dispersion problem (2017)
  8. Karimi, Sahar; Ronagh, Pooya: A subgradient approach for constrained binary optimization via quantum adiabatic evolution (2017)
  9. Krislock, Nathan; Malick, Jérôme; Roupin, Frédéric: BiqCrunch: a semidefinite branch-and-bound method for solving binary quadratic problems (2017)