{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T18:25:16Z","timestamp":1783103116183,"version":"3.54.6"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,6,30]],"date-time":"2022-06-30T00:00:00Z","timestamp":1656547200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Austrian Science Fund","award":["I\u00a03199-N31"],"award-info":[{"award-number":["I\u00a03199-N31"]}]},{"DOI":"10.13039\/501100004329","name":"Slovenian Research Agency","doi-asserted-by":"crossref","award":["P2-0162, N1-0057, N1-0071, J1-2453, and J1-1691"],"award-info":[{"award-number":["P2-0162, N1-0057, N1-0071, J1-2453, and J1-1691"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"crossref"}]},{"name":"European Union\u2019s Horizon\u00a02020"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2022,6,30]]},"abstract":"<jats:p>We present BiqBin, an exact solver for linearly constrained binary quadratic problems. Our approach is based on an exact penalty method to first efficiently transform the original problem into an instance of Max-Cut, and then to solve the Max-Cut problem by a branch-and-bound algorithm. All the main ingredients are carefully developed using new semidefinite programming relaxations obtained by strengthening the existing relaxations with a set of hypermetric inequalities, applying the bundle method as the bounding routine and using new strategies for exploring the branch-and-bound tree.<\/jats:p><jats:p>Furthermore, an efficient C implementation of a sequential and a parallel branch-and-bound algorithm is presented. The latter is based on a load coordinator-worker scheme using MPI for multi-node parallelization and is evaluated on a high-performance computer.<\/jats:p><jats:p>The new solver is benchmarked against BiqCrunch, GUROBI, and SCIP on four families of (linearly constrained) binary quadratic problems. Numerical results demonstrate that BiqBin is a highly competitive solver. The serial version outperforms the other three solvers on the majority of the benchmark instances. We also evaluate the parallel solver and show that it has good scaling properties. The general audience can use it as an on-line service available at<jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"url\" xlink:href=\"http:\/\/www.biqbin.eu\">http:\/\/www.biqbin.eu<\/jats:ext-link>.<\/jats:p>","DOI":"10.1145\/3514039","type":"journal-article","created":{"date-parts":[[2022,7,19]],"date-time":"2022-07-19T13:50:20Z","timestamp":1658238620000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["BiqBin: A Parallel Branch-and-bound Solver for Binary Quadratic Problems with Linear Constraints"],"prefix":"10.1145","volume":"48","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9422-2821","authenticated-orcid":false,"given":"Nicol\u00f2","family":"Gusmeroli","sequence":"first","affiliation":[{"name":"Alpen-Adria-Universit\u00e4t Klagenfurt, Klagenfurt, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4852-1986","authenticated-orcid":false,"given":"Timotej","family":"Hrga","sequence":"additional","affiliation":[{"name":"University of Ljubljana, Faculty of Mechanical Engineering, Ljubljana, Slovenia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8356-8827","authenticated-orcid":false,"given":"Borut","family":"Lu\u017ear","sequence":"additional","affiliation":[{"name":"Faculty of Information Studies, Novo mesto, Slovenia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9856-1476","authenticated-orcid":false,"given":"Janez","family":"Povh","sequence":"additional","affiliation":[{"name":"University of Ljubljana, Faculty of Mechanical Engineering, Ljubljana, Slovenia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9101-834X","authenticated-orcid":false,"given":"Melanie","family":"Siebenhofer","sequence":"additional","affiliation":[{"name":"Alpen-Adria-Universit\u00e4t Klagenfurt, Klagenfurt, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1670-7951","authenticated-orcid":false,"given":"Angelika","family":"Wiegele","sequence":"additional","affiliation":[{"name":"Alpen-Adria-Universit\u00e4t Klagenfurt, Klagenfurt, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,7,19]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01587084"},{"key":"e_1_3_2_3_2","article-title":"Heuristic algorithms for the unconstrained binary quadratic programming problem","volume":"4","author":"Beasley John E.","year":"1998","unstructured":"John E. Beasley. 1998. Heuristic algorithms for the unconstrained binary quadratic programming problem. London, England 4 (1998).","journal-title":"London, England"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.34"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1080\/03155986.2005.11732724"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.5555\/3112651.3112771"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-93964-1_1"},{"issue":"2","key":"e_1_3_2_8_2","first-page":"191\u2013216, 217\u201324","article-title":"Applications of cut polyhedra. I, II","volume":"55","author":"Deza Michel","year":"1994","unstructured":"Michel Deza and Monique Laurent. 1994. Applications of cut polyhedra. I, II. J. Comput. Appl. Math. 55, 2 (1994), 191\u2013216, 217\u2013247. JCAMDI","journal-title":"J. Comput. Appl. Math."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-009-0369-2_8"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.2172\/822567"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-018-0147-4"},{"key":"e_1_3_2_12_2","volume-title":"The SCIP Optimization Suite 7.0","author":"Gamrath Gerald","year":"2020","unstructured":"Gerald Gamrath, Daniel Anderson, Ksenia Bestuzheva, Wei-Kun Chen, Leon Eifler, Maxime Gasse, Patrick Gemander, Ambros Gleixner, Leona Gottwald, Katrin Halbig, Gregor Hendel, Christopher Hojny, Thorsten Koch, Pierre Le Bodic, Stephen J. Maher, Frederic Matter, Matthias Miltenberger, Erik M\u00fchmer, Benjamin M\u00fcller, Marc E. Pfetsch, Franziska Schl\u00f6sser, Felipe Serrano, Yuji Shinano, Christine Tawfik, Stefan Vigerske, Fabian Wegscheider, Dieter Weninger, and Jakob Witzig. 2020. The SCIP Optimization Suite 7.0. Technical Report. Optimization Online. http:\/\/www.optimization-online.org\/DB_HTML\/2020\/03\/7705.html."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.5555\/578533"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_3_2_15_2","unstructured":"Gurobi Optimization LLC. 2022. Gurobi Optimizer Reference Manual. https:\/\/www.gurobi.com."},{"key":"e_1_3_2_16_2","article-title":"EXPEDIS: Randomly Generated Instances","author":"Gusmeroli Nicol\u00f2","year":"2019","unstructured":"Nicol\u00f2 Gusmeroli. 2019. EXPEDIS: Randomly Generated Instances. https:\/\/www.aau.at\/en\/mathematics\/publications\/software\/. (2019).","journal-title":"https:\/\/www.aau.at\/en\/mathematics\/publications\/software\/"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2021.100622"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580072"},{"key":"e_1_3_2_19_2","first-page":"388","volume-title":"Advances in High Performance Computing, Proceedings of HPC2019 Conference (HPC\u201919)","author":"Hrga Timotej","year":"2020","unstructured":"Timotej Hrga, Borut Lu\u017ear, Janez Povh, and Angelika Wiegele. 2020. BiqBin: Moving boundaries for NP-hard problems by HPC. In Advances in High Performance Computing, Proceedings of HPC2019 Conference (HPC\u201919). 388\u2013405."},{"key":"e_1_3_2_20_2","article-title":"MADAM: A parallel exact solver for Max-Cut based on semidefinite programming and ADMM","author":"Hrga Timotej","year":"2020","unstructured":"Timotej Hrga and Janez Povh. 2020. MADAM: A parallel exact solver for Max-Cut based on semidefinite programming and ADMM. arXiv preprint arXiv:2010.07839 (2020).","journal-title":"arXiv preprint arXiv:2010.07839"},{"key":"e_1_3_2_21_2","unstructured":"IBM. 2009. IBM ILOG CPLEX V12.1: User\u2019s Manual for CPLEX. (2009). ftp:\/\/public.dhe.ibm.com\/software\/websphere\/ilog\/docs\/optimization\/cplex\/ps_usrmancplex.pdf."},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-7138-7"},{"key":"e_1_3_2_23_2","first-page":"85","volume-title":"Complexity of Computer Computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972)","author":"Karp Richard M.","year":"1972","unstructured":"Richard M. Karp. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972). Plenum, New York, 85\u2013103."},{"key":"e_1_3_2_24_2","series-title":"Math. Appl. (Japanese Ser.)","first-page":"263","volume-title":"Mathematical Programming (Tokyo, 1988)","author":"Kiwiel Krzysztof C.","year":"1989","unstructured":"Krzysztof C. Kiwiel. 1989. A survey of bundle methods for nondifferentiable optimization. In Mathematical Programming (Tokyo, 1988). Math. Appl. (Japanese Ser.), Vol. 6. SCIPRESS, Tokyo, 263\u2013282."},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-012-0594-z"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3005345"},{"key":"e_1_3_2_27_2","article-title":"Densest k-subgraph Problem, Benchmark Instances","author":"Lambert Am\u00e9lie","year":"2018","unstructured":"Am\u00e9lie Lambert. 2018. Densest k-subgraph Problem, Benchmark Instances. http:\/\/cedric.cnam.fr\/ lamberta\/Library\/k-cluster.html. (2018). Accessed: 2018-02-27.","journal-title":"http:\/\/cedric.cnam.fr\/ lamberta\/Library\/k-cluster.html"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2015.12.014"},{"key":"e_1_3_2_29_2","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1002\/3527603794.ch4","volume-title":"New Optimization Algorithms in Physics","author":"Liers Frauke","year":"2004","unstructured":"Frauke Liers, Michael J\u00fcnger, Gerhard Reinelt, and Giovanni Rinaldi. 2004. Computing exact ground states of hard ising spin glass problems by branch-and-cut. In New Optimization Algorithms in Physics, Alexander Hartmann and Heiko Rieger (Eds.). Wiley, 47\u201368."},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-016-9856-7"},{"key":"e_1_3_2_31_2","unstructured":"miplib2017 2018. MIPLIB 2017. (2018). miplib.zib.de."},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.4208\/cicp.110113.010813a"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/bf02247879"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02023057"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2006.08.007"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-008-0235-8"},{"key":"e_1_3_2_37_2","article-title":"Rudy","author":"Rinaldi Giovanni","year":"1998","unstructured":"Giovanni Rinaldi. 1998. Rudy. http:\/\/www-user.tu-chemnitz.de\/ helmberg\/rudy.tar.gz. (1998).","journal-title":"http:\/\/www-user.tu-chemnitz.de\/ helmberg\/rudy.tar.gz"},{"key":"e_1_3_2_38_2","volume-title":"Combinatorial Optimization: Disjoint Paths, Hypergraphs","author":"Schrijver Alexander","year":"2003","unstructured":"Alexander Schrijver. 2003. Combinatorial Optimization: Disjoint Paths, Hypergraphs. Springer. 2002036693https:\/\/books.google.si\/books?id=HNcpAQAAMAAJ"},{"key":"e_1_3_2_39_2","first-page":"161","volume-title":"SOR\u201919 Proceedings","author":"Kalamar Alen Vegi","year":"2019","unstructured":"Alen Vegi Kalamar, Drago Bokal, and Janez Povh. 2019. Parallelization of BiqMac solver. In SOR\u201919 Proceedings. Slovenian Society Informatika, Section for Operational Research, 161\u2013166."},{"key":"e_1_3_2_40_2","article-title":"BiqMac Library","author":"Wiegele Angelika","year":"2007","unstructured":"Angelika Wiegele. 2007. BiqMac Library. http:\/\/biqmac.aau.at\/biqmaclib.html. (2007).","journal-title":"http:\/\/biqmac.aau.at\/biqmaclib.html"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1038\/nmeth.3583"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2014.09.064"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNN.2005.845141"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3514039","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3514039","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:02:35Z","timestamp":1750186955000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3514039"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,30]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6,30]]}},"alternative-id":["10.1145\/3514039"],"URL":"https:\/\/doi.org\/10.1145\/3514039","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,30]]},"assertion":[{"value":"2020-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-07-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}