×

zbMATH — the first resource for mathematics

PEBBL: an object-oriented framework for scalable parallel branch and bound. (English) Zbl 1329.90171
Summary: Parallel Enumeration and Branch-and-Bound Library (PEBBL) is a C++ class library implementing the underlying operations needed to support a wide variety of branch-and-bound algorithms on MPI-based message-passing distributed-memory parallel computing environments. PEBBL can be customized to support application-specific operations, while managing the generic aspects of branch and bound, such as maintaining the active subproblem pool across multiple processors, load balancing, and termination detection. PEBBL is designed to provide highly scalable performance on large numbers of processor cores. We describe the basics of PEBBL’s architecture, with emphasis on the features most critical to is high scalability, including its flexible two-level load balancing architecture and its support for a synchronously parallel ramp-up phase. We also present an example application: the maximum monomial agreement problem arising from certain machine learning applications. For sufficiently difficult problem instances, we show essentially linear speedup on over 6000 processor cores, demonstrating a new state of the art in scalability for branch-and-bound implementations. We also show how processor cache effects can lead to reproducibly superlinear speedups.

MSC:
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
65Y05 Parallel numerical computation
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Asuncion, A., Newman, D.J.: UCI machine learning repository (2007). http://www.ics.uci.edu/ mlearn/MLRepository.html
[2] Bader, DA; Hart, WE; Phillips, CA; Greenberg, HJ (ed.), Parallel algorithm design for branch and bound, 5-1-5-44, (2004), Dordrecht
[3] Benaïchouche, M., Cung, V.D., Dowaji, S., Cun, B.L., Mautor, T., Roucairol, C.: Building a parallel branch and bound library. In: Solving Combinatorial Optimization Problems in Parallel—Methods and Techniques, Lecture Notes in Computer Science, vol. 1054, pp. 201-231. Springer-Verlag, London (1996) · Zbl 1062.90039
[4] Bendjoudi, A., Melab, N., Talbi, E.G.: Fault-tolerant mechanism for hierarchical branch and bound algorithm. In: Workshops Proceedings, 25th IEEE International Parallel and Distributed Processing Symposium, Workshop on Large-Scale Parallel Processing (LSPP), pp. 1806-1814. Anchorage, Alaska (20011)
[5] Blelloch, GE, Scans as primitive parallel operations, IEEE Trans. Comput., 38, 1526-1538, (1989)
[6] Boros, E; Hammer, PL; Ibaraki, T; Kogan, A, Logical analysis of numerical data, Math. Program., 79, 163-190, (1997) · Zbl 0887.90179
[7] Brewer, T.: A highly scalable system utilizing up to 128 PA-RISC processors. In: COMPCON, Technologies for the Information Superhighway, Digest of Papers, pp. 133-140 (1995). http://dblp.uni-trier.de/db/conf/compcon/compcon95.html#Brewer95 · Zbl 0806.90095
[8] Cataldo, A.M., Whaley, R.C.: Scaling LAPACK panel operations using parallel cache assignment. In: ACM Principles and Practice of Parallel Programming. ACM, New York (2010) · Zbl 0998.68105
[9] Clausen, J; Migdalas, A (ed.); Pardalos, P (ed.); Storøy, S (ed.), Branch and bound algorithms—principles and examples, No. 7, 239-267, (1997), Dordrecht · Zbl 0903.90123
[10] Clausen, J; Perregaard, M, On the best search strategy in parallel branch-and-bound: best-first search versus lazy depth-first search, Ann. Oper. Res., 90, 1-17, (1999) · Zbl 0937.90089
[11] Danna, E., Fenelon, M., Gu, Z., Wunderling, R.: Generating multiple solutions for mixed integer programming problems. In: Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, vol. 4513, pp. 280-294. Springer, Berlin (2007) · Zbl 1136.90416
[12] Demiriz, A; Bennett, KP; Shawe-Taylor, J, Linear programming boosting via column generation, Mach. Learn., 46, 225-254, (2002) · Zbl 0998.68105
[13] Dobkin, DP; Gunopulos, D; Maass, W, Computing the maximum bichromatic discrepancy, with applications to computer graphics and machine learning, J. Comp. Syst. Sci., 52, 453-470, (1996) · Zbl 0858.68077
[14] Eckstein, J.: Control strategies for parallel mixed integer branch and bound. In: Supercomputing ’94: Proceedings of the 1994 ACM/IEEE conference on Supercomputing, pp. 41-48. ACM, New York (1994) · Zbl 1147.90416
[15] Eckstein, J, Parallel branch-and-bound algorithms for general mixed integer programming on the CM-5, SIAM J. Optim., 4, 794-814, (1994) · Zbl 0819.90063
[16] Eckstein, J, Distributed versus centralized storage and control for parallel branch and bound: mixed integer programming on the CM-5, Comput. Optim. Appl., 7, 199-220, (1997) · Zbl 0881.90100
[17] Eckstein, J, How much communication does parallel branch and bound need?, INFORMS J. Comput., 9, 15-29, (1997) · Zbl 0890.90148
[18] Eckstein, J; Goldberg, N, An improved branch-and-bound method for maximum monomial agreement, INFORMS J. Comput., 24, 328-341, (2012) · Zbl 06599273
[19] Eckstein, J., Hart, W.E., Phillips, C.: Massively parallel mixed-integer programming: algorithms and applications. In: Heroux, M.A., Raghavan, P., Simon, H. (eds.) Parallel Processing for Scientific Computing, chapter 17, pp. 323-340. Based on the 11th SIAM Conference on Parallel Processing for Scientific Computing. SIAM (2006) · Zbl 0911.90282
[20] Eckstein, J., Hart, W.E., Phillips, C.A.: Resource management in a parallel mixed integer programming package. In: Proceedings of the Intel Supercomputer Users Group (1997). Online proceedings
[21] Eckstein, J., Phillips, C.A., Hart, W.E.: PICO: An object-oriented framework for parallel branch and bound. In: Inherently parallel algorithms in feasibility and optimization and their applications (Haifa, 2000), Stud. Comput. Math., vol. 8, pp. 219-265. North-Holland, Amsterdam (2001) · Zbl 0989.90130
[22] Eckstein, J., Phillips, C.A., Hart, W.E.: PEBBL: An object-oriented framework for scalable parallel branch and bound. RUTCOR Research Report RRR 9-2013, Rutgers University (2013) · Zbl 1329.90171
[23] Eckstein, J., Phillips, C.A., Hart, W.E.: PEBBL 1.4.1 user’s guide. RUTCOR Research Report RRR 2-2014, Rutgers University (2014)
[24] Elf, M., Gutwenger, C., Jünger, M., Rinaldi, G.: Branch-and-cut algorithms for combinatorial optimization and their implementation in ABACUS. In: Computational Combinatorial Optimization, Optimal or Provably Near-Optimal Solutions, pp. 157-222. Springer-Verlag, London (2001) · Zbl 1052.90106
[25] Goldberg, N., Shan, C.: Boosting optimal logical patterns. In: Proceedings of the Seventh SIAM International Conference on Data Mining, pp. 228-236. SIAM, Minneapolis (2007) · Zbl 0887.90179
[26] Graham, R.L., Woodall, T.S., Squyres, J.M.: Open MPI: A flexible high performance MPI. In: Proceedings, 6th Annual International Conference on Parallel Processing and Applied Mathematics. Poznan, Poland (2005) · Zbl 0875.68206
[27] Gropp, W; Lusk, E; Doss, N; Skjellum, A, High-performance, portable implementation of the MPI message passing interface standard, Parallel Comput., 22, 789-828, (1996) · Zbl 0875.68206
[28] Hillis, W.D.: The Connection Machine. MIT Press, Cambridge (1985)
[29] Ichnowski, J., Alterovitz, R.: Parallel sampling-based motion planning with superlinear speedup. In: IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 1206-1212 (2012) · Zbl 0858.68077
[30] Jünger, M; Thienel, S, Introduction to ABACUS-a branch-and-cut system, Oper. Res. Lett., 22, 83-95, (1998) · Zbl 0911.90282
[31] Jünger, M; Thienel, S, The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization, Software Pract. Expert., 30, 1325-1352, (2000) · Zbl 1147.90416
[32] Karypis, G., Kumar, V.: Unstructured tree search on SIMD parallel computers: a summary of results. In: Supercomputing ’92: Proceedings of the 1992 ACM/IEEE conference on Supercomputing, pp. 453-462. IEEE Computer Society Press, Los Alamitos (1992)
[33] Kearns, MJ; Schapire, RE; Sellie, LM, Toward efficient agnostic learning, Mach. Learn., 17, 115-141, (1994) · Zbl 0938.68797
[34] Kim, M., Lee, H., Lee;, J.: A proportional-share scheduler for multimedia applications. In: IEEE International Conference on Multimedia computing and systems ’97, pp. 484-491. IEEE Computer Society Press, Los Alamitos (1997)
[35] Koch, T; Ralphs, T; Shinano, Y, Could we use a millon cores to solve an integer program?, Math. Methods Oper. Res., 76, 67-93, (2012) · Zbl 1262.90106
[36] Ladányi, L., Ralphs, T.K., Trotter Jr., L.E.: Branch, cut, and price: Sequential and parallel. In: Computational combinatorial optimization (Schloß Dagstuhl, 2000), Lecture Notes in Computer Science, vol. 2241, pp. 223-260. Springer, Berlin (2001) · Zbl 1052.90107
[37] Mahanti, A; Daniel, CJ, A SIMD approach to parallel heuristic search, Artif. Intel., 60, 243-282, (1993)
[38] Mattern, F, Algorithms for distributed termination detection, Distrib. Comput., 2, 161-175, (1987)
[39] Menouer, T., LeCun, B., Vander-Swalmen, P.: Partitioning methods to parallelize constraint programming solver using the parallel framework BobPP. In: Proceedings of the First International Conference on Computer Science, Applied Mathematics and Applications (ICCSAMA), pp. 117-127. Springer International Publishing, Switzerland (2013)
[40] Nemhauser, GL; Savelsbergh, MWP; Sigismondi, GC, MINTO, a mixed integer optimizer, Oper. Res. Lett., 15, 47-58, (1994) · Zbl 0806.90095
[41] Ralphs, TK; Ladányi, L; Saltzman, MJ, Parallel branch, cut, and price for large-scale discrete optimization, Math. Program. Ser. B, 98, 253-280, (2003) · Zbl 1082.90102
[42] Ralphs, TK; Ládanyi, L; Saltzman, MJ, A library hierarchy for implementing scalable parallel search algorithms, J. Supercomput., 28, 215-234, (2004) · Zbl 1062.90039
[43] Rayward-Smith, VJ; Rush, SA; McKeown, GP, Efficiency considerations in the implementation of parallel branch-and-bound, Ann. Oper. Res., 43, 123-145, (1993) · Zbl 0784.90108
[44] Schulz, M; Galarowicz, J; Maghrak, D; Hachfeld, W; Montoya, D; Cranford, S, Open\(|\)speedshop: an open source infrastructure for parallel performance analysis, Sci. Program., 16, 105-121, (2008)
[45] Shinano, Y.: ParaSCIP and fiberSCIP libraries to parallelize a customized SCIP solver (2014). http://scip.zib.de/workshop/parascip_libraries.pdf. SCIP Workshop 2014
[46] Shinano, Y., Achterberg, T., Berthold, T., Heinz, S., Koch, T.: paraSCIP: a parallel extension of SCIP. In: Competence in High Performance Computing 2010, pp. 135-148. Springer-Verlag, Belin Heidelberg (2012)
[47] Shinano, Y., Harada, K., Hirabayashi, R.: Control schemes in a generalized utility for parallel branch-and-bound algorithms. In: IPPS ’97: Proceedings of the 11th International Symposium on Parallel Processing, p. 621. IEEE Computer Society, Washington, DC (1997)
[48] Shinano, Y., Higaki, M., Hirabayashi, R.: A generalized utility for parallel branch and bound algorithms. In: SPDP ’95: Proceedings of the 7th IEEE Symposium on Parallel and Distributeed Processing, p. 392. IEEE Computer Society, Washington, DC (1995)
[49] Snir, M., Otto, S.W., Walker, D.W., Dongarra, J., Huss-Lederman, S.: MPI: The Complete Reference. MIT Press, Cambridge (1995)
[50] Tschöke, S., Polzer, T.: Portable parallel branch-and-bound library: PPBB-Lib user manual version 2.0. Tech. rep., Department of Computer Science, University of Paderborn (1996) · Zbl 06599273
[51] Waldspurger, C.A.: Lottery and stride scheduling: flexibile proportional-share resource management. Ph.D. thesis, MIT Department of Electrical Engineering and Computer Science, Cambridge (1996) · Zbl 06599273
[52] Wu, M.S., Aluru, S., Kendall, R.A.: Mixed mode matrix multiplication. In: Proceedings of the IEEE International Conference on Cluster Computing, pp. 195-203 (2002)
[53] Wu, X. (ed.): Performance Evaluation, Prediction and Visualization of Parallel Systems, vol. 4 of The Kluwer International Series on Asian Studies in Computer and Information Science. Kluwer Academic, Springer (1999) · Zbl 0927.68035
[54] Xu, Y., Ralphs, T.K., Ladányi, L., Saltzman, M.J.: Computational experience with a software framework for parallel integer programming. INFORMS J. Comput. 21, 383-397 (2009). http://coral.ie.lehigh.edu/ ted/files/papers/CHiPPS-Rev.pdf · Zbl 1243.90010
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.