×

BiqBin: moving boundaries for NP-hard problems by HPC. (English) Zbl 1440.90061

Dimov, Ivan (ed.) et al., Advances in high performance computing. Results of the international conference on high performance computing, Borovets, Bulgaria, September 2–6, 2019. Cham: Springer. Stud. Comput. Intell. 902, 327-339 (2021).
Summary: In this paper we present a parallel Branch and Bound (B&B) algorithm to solve the Stable Set Problem, which is a well-known combinatorial optimization problem. The algorithm is based on tight semidefinite programming bounds. Numerical results, based on using up to 192 CPU cores, show that this algorithm scales well.
This algorithm is available as a part of the online BiqBin solver, which enables online submissions of problem instances. After submission, it automatically generates computational jobs and runs them using the high-performance computer available at University of Ljubljana. BiqBin demonstrates how to bring HPC closer to specific user community – in our case the mathematical optimization community.
For the entire collection see [Zbl 1440.65005].

MSC:

90C27 Combinatorial optimization
65K05 Numerical mathematical programming methods
65Y10 Numerical algorithms for specific classes of architectures
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

Software:

BiqCrunch; BiqBin; BiqMac; MKL
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Intel Math Kernel Library. Reference Manual. Intel Corporation (2009)
[2] Anjos, M.F., Lasserre, J.B. (eds.): Handbook on Semidefinite, Conic and Polynomial Optimization. International Series in Operations Research & Management Science, vol. 166. Springer, New York (2012) · Zbl 1235.90002
[3] Boyd, S., Mattingley, J.: Branch and Bound Methods (2007)
[4] Clausen, J.: Branch and Bound Algorithms - Principles and Examples, pp. 1-30. Department of Computer Science, University of Copenhagen (1999)
[5] Cottle, R.W., Thapa, M.N.: Linear and Nonlinear Optimization. International Series in Operations Research & Management Science. Springer, New York (2017) · Zbl 1514.90159 · doi:10.1007/978-1-4939-7055-1
[6] Message Passing Interface Forum: MPI: A message-passing interface standard. Technical report, Knoxville, TN, USA (1994)
[7] James, G., Witten, D., Hastie, T., Tibshirani, R.: An Introduction to Statistical Learning: with Applications in R. Springer Texts in Statistics, vol. 103. Springer, New York (2013) · Zbl 1281.62147
[8] Johnson, D.S., Trick, M.A.: Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11-13, 1993, vol. 26. American Mathematical Soc. (1996) · Zbl 0875.68678
[9] Krislock, N., Malick, J., Roupin, F.: BiqCrunch User Guide (2014)
[10] Lasserre, J.B.: A max-cut formulation of 0/1 programs. Oper. Res. Lett. 44(2), 158-164 (2016) · Zbl 1408.90222 · doi:10.1016/j.orl.2015.12.014
[11] Malick, J., Povh, J., Rendl, F., Wiegele, A.: Regularization methods for semidefinite programming. SIAM J. Optim. 20, 336-356 (2009) · Zbl 1187.90219 · doi:10.1137/070704575
[12] Povh, J.: Semidefinite approximations for quadratic programs over orthogonal matrices. J. Global Optim. 48(3), 447-463 (2009) · Zbl 1203.90121 · doi:10.1007/s10898-009-9499-7
[13] Povh, J.: Contribution of copositive formulations to the graph partitioning problem. Optimization 62(1), 71-83 (2013) · Zbl 1291.90166 · doi:10.1080/02331934.2011.560385
[14] Povh, J., Rendl, F.: Copositive and semidefinite relaxations of the quadratic assignment problem. Discret. Optim. 6(3), 231-241 (2009) · Zbl 1167.90597 · doi:10.1016/j.disopt.2009.01.002
[15] Povh, J., Rendl, F., Wiegele, A.: A boundary point method to solve semidefinite programs. Computing 78, 277-286 (2006) · Zbl 1275.90055 · doi:10.1007/s00607-006-0182-2
[16] Rendl, F., Rinaldi, G., Wiegele, A.: BiqMac – a solver for binary quadratic and max-cut problems (2006). http://BiqMac.aau.at/
[17] Rendl, F., Rinaldi, G., Wiegele, A.: Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations. Math. Program. 121(2, Ser. A), 307-335 (2010) · Zbl 1184.90118 · doi:10.1007/s10107-008-0235-8
[18] Sanderson, C., Curtin, R.: Armadillo: a template-based c++ library for linear algebra. J. Open Source Soft. 1(2), 26 (2016) · doi:10.21105/joss.00026
[19] Rui, X., Donald Wunsch, I.I.: Survey of clustering algorithms. IEEE Trans. Neural Netw. 16(3), 645-678 (2005) · doi:10.1109/TNN.2005.845141
[20] Yang, X.
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.