Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 11

Proceedings of the 2017 Federated Conference on Computer Science and Information Systems

Solving 0-1 Quadratic Problems with Two-Level Parallelization of the BiqCrunch Solver

, ,

DOI: http://dx.doi.org/10.15439/2017F329

Citation: Proceedings of the 2017 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 11, pages 445–452 ()

Full text

Abstract. In this paper we present MLTBiqCrunch, a hierarchically parallelized version of the open-source solver BiqCrunch. More precisely, this version has two levels of parallelization: a coarse grain, assigning a thread to a node evaluation and a fine grain, parallelizing a node evaluation when some threads are not busy. We present experiments on some classical binary quadratic optimization problems with comparison of their scalability and raw performance. In particular, we obtain a superlinear speedup for some of the most difficult instances.

References

  1. N. Krislock, J. Malick, and F. Roupin, “Biqcrunch: A semidefinite branch-and-bound method for solving binary quadratic problems,” ACM Trans. Math. Softw., vol. 43, no. 4, pp. 32:1–32:23, Jan. 2017. http://dx.doi.org/10.1145/3005345. [Online]. Available: http://doi.acm.org/10.1145/3005345
  2. S. Burer and A. Letchford, “Non-convex mixed-integer nonlinear programming: A survey,” Surveys in Operations Research and Management Science, vol. 17, no. 2, pp. 97 – 106, 2012. http://dx.doi.org/10.1016/j.sorms.2012.08.001. [Online]. Available: https://doi.org/10.1016/j.sorms.2012.08.001
  3. M. Bussieck, S. Vigerske, J. Cochran, L. Cox, P. Keskinocak, J. Kharoufeh, and J. Smith, MINLP Solver Software. John Wiley, Inc., 2010, updated Feb 21, 2012. [Online]. Available: https://doi.org/10.1002/9780470400531.eorms0527
  4. CPLEX, IBM ILOG CPLEX V12.1 User’s Manual for CPLEX, IBM Corporation, 2009.
  5. B. Borchers and J. G. Young, “implementation of a primaldual method for sdp on a shared memory parallel architecture,” Computational Optimization and Applications, vol. 3, no. 37, pp. 355–369, 2007. http://dx.doi.org/10.1007/s10589-007-9030-3. [Online]. Available: https://doi.org/10.1007/s10589-007-9030-3
  6. L. Barreto and M. Bauer, “Parallel branch and bound algorithm - a comparison between serial, openmp and mpi implementations,” Journal of Physics: Conference Series, vol. 256, no. 1, p. 012018, 2010. [Online]. Available: http://stacks.iop.org/1742-6596/256/i=1/a=012018
  7. A. Bendjoudi, N. Melab, and E.-G. Talbi, “Hierarchical branch and bound algorithm for computational grids,” Future Generation Computer Systems, vol. 28, no. 8, pp. 1168– 1176, 2012. http://dx.doi.org/10.1016/j.future.2012.03.001. [Online]. Available: https://doi.org/10.1016/j.future.2012.03.001
  8. J. Gmys, M. Mezmaz, N. Melab, and D. Tuyttens, “Ivmbased parallel branch-and-bound using hierarchical work stealing on multi-gpu systems,” Concurrency and Computation: Practice and Experience, 2016. http://dx.doi.org/10.1002/cpe.4019. [Online]. Available: https://doi.org/10.1002/cpe.4019
  9. D. A. Bader, W. E. Hart, and C. A. Phillips, Tutorials on Emerging Methodologies and Applications in Operations Research. Chapter 5 : Parallel Algorithm Design for Branch and Bound, h.j. greenberg, editor ed. Philadelphia, PA: Society for Industrial and Applied Mathematics, Kluwer Academic Press, 2004.
  10. Y. Xu, T. Ralphs, L. Ladanyi, and M. Saltzman, “Coin-or high-performance parallel search framework,” projects.coin-or.org/CHiPPS.
  11. J. Malick and F. Roupin, “On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds for 0–1 quadratic problems leading to quasi-newton methods,” Mathematical Programming, vol. 140, no. 1, pp. 99–124, 2013. http://dx.doi.org/10.1007/s10107-012-0628-6. [Online]. Available: http://dx.doi.org/10.1007/s10107-012-0628-6
  12. N. Melab, J. Gmys, M. Mezmaz, and D. Tuyttens, “Multicore versus many-core computing for many-task branch-and-bound applied to big optimization problems,” Future Generation Computer Systems, 2017. http://dx.doi.org/10.1016/j.future.2016.12.039. [Online]. Available: https://doi.org/10.1016/j.future.2016.12.039
  13. I. Chakroun and N. Melab, “Towards a heterogeneous and adaptive parallel branch-and-bound algorithm,” Journal of Computer and System Sciences, vol. 81, no. 1, pp. 72–84, 2015. http://dx.doi.org/10.1016/j.jcss.2014.06.012. [Online]. Available: https://doi.org/10.1016/j.jcss.2014.06.012
  14. E. Anderson, Z. Bai, C. Bischof, S. Blackford, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, and D. Sorensen, LAPACK Users’ Guide, 3rd ed. Philadelphia, PA: Society for Industrial and Applied Mathematics, 1999. [Online]. Available: https://doi.org/10.1137/1.9780898719604.pt2
  15. C. Zhu, R. Byrd, P. Lu, and J. Nocedal, “Algorithm 778: L-bfgs-b: Fortran subroutines for large-scale bound-constrained optimization,” ACM Trans. Math. Softw., vol. 23, no. 4, pp. 550–560, Dec. 1997. [Online]. Available: https://doi.org/10.1137/0916069
  16. J. Morales and J. Nocedal, “Remark on “Algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound constrained optimization”,” ACM Trans. Math. Softw., vol. 38, no. 1, pp. 1–4, 2011. [Online]. Available: https://doi.org/10.1145/2049662.2049669
  17. B. Le Cun, C. Roucairol, and T. P. Team, “Bob: a unified platform for implementing branch-and-bound like algorithms,” Laboratoire Prism, Tech. Rep., 1995.
  18. F. Rendl, G. Rinaldi, and A. Wiegele, A Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations. Berlin, Heidelberg: Springer Berlin Heidelberg, 2007, pp. 295–309. ISBN 978-3-540-72792-7. [Online]. Available: http://dx.doi.org/10.1007/978-3-540-72792-7 23
  19. N. Krislock, J. Malick, and F. Roupin, “Improved semidefinite bounding procedure for solving max-cut problems to optimality,” Mathematical Programming, vol. 143, no. 1, pp. 61–86, 2014. http://dx.doi.org/10.1007/s10107- 012-0594-z. [Online]. Available: https://doi.org/10.1007/s10107-012- 0594-z
  20. E. D. Dolan and J. J. Moré, “Benchmarking optimization software with performance profiles,” Mathematical Programming, vol. 91, pp. 201– 213, 2002. [Online]. Available: https://doi.org/10.1007/s101070100263
  21. N. Krislock, J. Malick, and F. Roupin, “Computational results of a semidefinite branch-and-bound algorithm for k-cluster,” Computers and Operations Research, vol. 66, pp. 153–159, 2016.
  22. M. Nakata, “The MPACK (MBLAS/MLAPACK); a multiple precision arithmetic version of blas and lapack,” mplapack.sourceforge.net/.
  23. X. Li, J. Demmel, D. Bailey, Y. Hida, J. Iskandar, A. Kapur, M. Martin, B. Thompson, T. Tung, and D. Yoo, “XBLAS–extra precise basic linear algebra subroutines,” http://www.netlib.org/xblas.