×
Gusmeroli, Nicolò; Hrga, Timotej; Lužar, Borut; Povh, Janez; Siebenhofer, Melanie; Wiegele, Angelika

BiqBin: a parallel branch-and-bound solver for binary quadratic problems with linear constraints. (English) Zbl 07666973

ACM Trans. Math. Softw. 48, No. 2, Article No. 15, 31 p. (2022).

Cited in 3 Documents

MSC:

65-XX Numerical analysis

Keywords:

solvers; semidefinite programming; binary quadratic programming; parallel algorithms

Software:

QPLIB; SCIP; BiqBin; MADAM; BiqCrunch; Biq Mac; ISLR; CPLEX; Rudy; BiqMac; Gurobi; MIPLIB
Cite Review PDF
Full Text: DOI arXiv

References:

[1] Barahona, Francisco, Jünger, Michael, and Reinelt, Gerhard. 1989. Experiments in quadratic 0-1 programming. Math. Program. Ser. A44, 2 (1989), 127-137. MHPGA4 · Zbl 0677.90046
[2] Beasley, John E.. 1998. Heuristic algorithms for the unconstrained binary quadratic programming problem. London, England4 (1998).
[3] Bhaskara, Aditya, Charikar, Moses, Vijayaraghavan, Aravindan, Guruswami, Venkatesan, and Zhou, Yuan. 2012. Polynomial integrality gaps for strong SDP relaxations of densest k-subgraph. In Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’12). SIAM, 388-405. http://dl.acm.org/citation.cfm?id=2095116.2095150 · Zbl 1423.68202
[4] Billionnet, Alain. 2005. Different formulations for solving the heaviest k-subgraph problem. INFOR Inf. Syst. Oper. Res.43, 3 (2005), 171-186. · Zbl 07682442
[5] Billionnet, Alain and Elloumi, Sourour. 2007. Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem.Math. Program. Ser. A109, 1 (2007), 55-68. · Zbl 1278.90263
[6] Das, Swagatam, Abraham, Ajith, and Konar, Amit. 2009. Metaheuristic pattern clustering-an overview. In Metaheuristic Clustering. Springer, 1-62. · Zbl 1221.62092
[7] Deza, Michel and Laurent, Monique. 1994. Applications of cut polyhedra. I, II. J. Comput. Appl. Math.55, 2 (1994), 191-216, 217-247. JCAMDI · Zbl 0826.52013
[8] Pillo, Gianni Di. 1994. Exact penalty methods. In Algorithms for Continuous Optimization. Springer, 209-253. · Zbl 0828.90128
[9] Dolan, Elizabeth D.. 2001. The NEOS Server 4.0 Administrative Guide. Technical Memorandum ANL/MCS-TM-250. Mathematics and Computer Science Division, Argonne National Laboratory.
[10] Furini, Fabio, Traversi, Emiliano, Belotti, Pietro, Frangioni, Antonio, Gleixner, Ambros, Gould, Nick, Liberti, Leo, Lodi, Andrea, Misener, Ruth, Mittelmann, Hans, Sahinidis, Nikolaos, Vigerske, Stefan, and Wiegele, Angelika. 2019. QPLIB: A library of quadratic programming instances. Math. Program. Comput.11, 2 (2019), 237-265. · Zbl 1435.90099
[11] Gamrath, Gerald, Anderson, Daniel, Bestuzheva, Ksenia, Chen, Wei-Kun, Eifler, Leon, Gasse, Maxime, Gemander, Patrick, Gleixner, Ambros, Gottwald, Leona, Halbig, Katrin, Hendel, Gregor, Hojny, Christopher, Koch, Thorsten, Bodic, Pierre Le, Maher, Stephen J., Matter, Frederic, Miltenberger, Matthias, Mühmer, Erik, Müller, Benjamin, Pfetsch, Marc E., Schlösser, Franziska, Serrano, Felipe, Shinano, Yuji, Tawfik, Christine, Vigerske, Stefan, Wegscheider, Fabian, Weninger, Dieter, and Witzig, Jakob. 2020. The SCIP Optimization Suite 7.0. Technical Report. Optimization Online. http://www.optimization-online.org/DB_HTML/2020/03/7705.html.
[12] Garey, Michael R. and Johnson, David S.. 1979. Computers and Intractability. W. H. Freeman and Co., San Francisco, Calif. x+338 pages. A guide to the theory of NP-completeness, A Series of Books in the Mathematical Sciences. · Zbl 0411.68039
[13] Goemans, Michel X. and Williamson, David P.. 1995. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. Assoc. Comput. Mach.42, 6 (1995), 1115-1145. JACOAH · Zbl 0885.68088
[14] Gurobi Optimization, LLC. 2022. Gurobi Optimizer Reference Manual. https://www.gurobi.com.
[15] Gusmeroli, Nicolò. 2019. EXPEDIS: Randomly Generated Instances. https://www.aau.at/en/mathematics/publications/software/. (2019).
[16] Gusmeroli, Nicolò and Wiegele, Angelika. 2021. EXPEDIS: An exact penalty method over discrete sets. Discrete Optimization (2021), 100622. DOI: · Zbl 1510.90200
[17] Helmberg, Christoph and Rendl, Franz. 1998. Solving quadratic \((0,1) \) -problems by semidefinite programs and cutting planes. Math. Program. Ser. A82, 3 (1998), 291-315. MHPGA4 · Zbl 0919.90112
[18] Hrga, Timotej, Lužar, Borut, Povh, Janez, and Wiegele, Angelika. 2020. BiqBin: Moving boundaries for NP-hard problems by HPC. In Advances in High Performance Computing, Proceedings of HPC2019 Conference (HPC’19). 388-405.
[19] Hrga, Timotej and Povh, Janez. 2020. MADAM: A parallel exact solver for Max-Cut based on semidefinite programming and ADMM. arXiv preprint arXiv:2010.07839 (2020).
[20] IBM. 2009. IBM ILOG CPLEX V12.1: User’s Manual for CPLEX. (2009). ftp://public.dhe.ibm.com/software/websphere/ilog/docs/optimization/cplex/ps_usrmancplex.pdf.
[21] James, Gareth, Witten, Daniela, Hastie, Trevor, and Tibshirani, Robert. 2013. An Introduction to Statistical Learning. , Vol. 103. Springer, New York. xiv+426 pages. DOI:With applications in R. · Zbl 1281.62147
[22] Karp, Richard M.. 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-103. · Zbl 1467.68065
[23] Kiwiel, Krzysztof C.. 1989. A survey of bundle methods for nondifferentiable optimization. In Mathematical Programming (Tokyo, 1988). , Vol. 6. SCIPRESS, Tokyo, 263-282. · Zbl 0683.90074
[24] Krislock, Nathan, Malick, Jérôme, and Roupin, Frédéric. 2014. Improved semidefinite bounding procedure for solving max-cut problems to optimality. Math. Program. Ser. A143, 1-2 (2014), 61-86. · Zbl 1285.90030
[25] Krislock, Nathan, Malick, Jérôme, and Roupin, Frédéric. 2017. BiqCrunch: A semidefinite branch-and-bound method for solving binary quadratic problems. ACM Trans. Math. Software (TOMS)43, 4 (2017), 1-23. · Zbl 1380.90284
[26] Lambert, Amélie. 2018. Densest k-subgraph Problem, Benchmark Instances. http://cedric.cnam.fr/ lamberta/Library/k-cluster.html. (2018). Accessed: 2018-02-27.
[27] Lasserre, Jean B.. 2016. A MAX-CUT formulation of 0/1 programs.Oper. Res. Lett.44, 2 (2016), 158-164. · Zbl 1408.90222
[28] Liers, Frauke, Jünger, Michael, Reinelt, Gerhard, and Rinaldi, Giovanni. 2004. Computing exact ground states of hard ising spin glass problems by branch-and-cut. In New Optimization Algorithms in Physics, Hartmann, Alexander and Rieger, Heiko (Eds.). Wiley, 47-68. · Zbl 1059.90147
[29] Lima, Ricardo M. and Grossmann, Ignacio E.. 2017. On the solution of nonconvex cardinality Boolean quadratic programming problems: A computational study. Comput. Optim. Appl.66, 1 (2017), 1-37. DOI: · Zbl 1371.90088
[30] miplib2017 2018. MIPLIB 2017. (2018). miplib.zib.de.
[31] Navarro, Cristobal A., Hitschfeld-Kahler, Nancy, and Mateu, Luis. 2014. A survey on parallel computing and its applications in data-parallel problems using GPU architectures. Commun. Comput. Phys.15, 2 (2014), 285-329. · Zbl 1388.65212
[32] Pardalos, Panos M. and Rodgers, Gregory P.. 1990. Computational aspects of a branch and bound algorithm for quadratic zero-one programming. Computing45, 2 (1990), 131-144. CMPTA2 · Zbl 0721.65034
[33] Pardalos, Panos M. and Rodgers, Gregory P.. 1990. Parallel branch and bound algorithms for quadratic zero-one programs on the hypercube architecture. Ann. Oper. Res.22, 1-4 (1990), 271-292. · Zbl 0722.90047
[34] Pisinger, David. 2007. The quadratic knapsack problem-a survey. Discrete Appl. Math.155, 5 (2007), 623-648. · Zbl 1143.90028
[35] Rendl, Franz, Rinaldi, Giovanni, and Wiegele, Angelika. 2010. Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations. Math. Program. Ser. A121, 2 (2010), 307-335. DOI: · Zbl 1184.90118
[36] Rinaldi, Giovanni. 1998. Rudy. http://www-user.tu-chemnitz.de/ helmberg/rudy.tar.gz. (1998).
[37] Schrijver, Alexander. 2003. Combinatorial Optimization: Disjoint Paths, Hypergraphs. Springer. https://books.google.si/books?id=HNcpAQAAMAAJ · Zbl 1041.90001
[38] Kalamar, Alen Vegi, Bokal, Drago, and Povh, Janez. 2019. Parallelization of BiqMac solver. In SOR’19 Proceedings. Slovenian Society Informatika, Section for Operational Research, 161-166.
[39] Wiegele, Angelika. 2007. BiqMac Library. http://biqmac.aau.at/biqmaclib.html. (2007).
[40] Wiwie, Christian, Baumbach, Jan, and Röttger, Richard. 2015. Comparing the performance of biomedical clustering methods. Nat. Methods12, 11 (2015), 1033.
[41] Wu, Qinghua and Hao, Jin-Kao. 2015. A review on algorithms for maximum clique problems. European J. Oper. Res.242, 3 (2015), 693-709. · Zbl 1341.05241
[42] Xu, Rui and II, Donald Wunsch. 2005. Survey of clustering algorithms. IEEE Trans. Neural Netw.16, 3 (2005), 645-678.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.