PEBBL swMATH ID: 13809 Software Authors: Eckstein, Jonathan; Hart, William E.; Phillips, Cynthia A. Description: PEBBL: an object-oriented framework for scalable parallel branch and bound. 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. Homepage: http://link.springer.com/article/10.1007%2Fs12532-015-0087-1 Keywords: branch and bound; parallel computation Related Software: FiberSCIP; SCIP; CHiPPS; ParaSCIP; UG; SYMPHONY; ALPS; XPRESS; GAMS; MIPLIB2003; BiCePS; MIPLIB; MINLPLib; ParaXpress; ParaLEX; CPLEX; ParSSSE; BLIS; PICO; MINOTAUR Cited in: 13 Documents Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year PEBBL: an object-oriented framework for scalable parallel branch and bound. Zbl 1329.90171Eckstein, Jonathan; Hart, William E.; Phillips, Cynthia A. 2015 all top 5 Cited by 30 Authors 4 Shinano, Yuji 3 Heinz, Stefan 2 Berthold, Timo 2 Eckstein, Jonathan 2 Palkar, Prashant 1 Asenjo, Rafael 1 Casado, Leocadio G. 1 Fischetti, Matteo 1 Goldberg, Noam 1 Hart, William E. 1 Hendrix, Eligius M. T. 1 Herrera, Juan F. R. 1 Knueven, Ben 1 Ladanyi, Laszlo 1 Monaci, Michele 1 Munguía, Lluís-Miquel 1 Ostrowski, Jim P. 1 Oxberry, Geoffrey M. 1 Phillips, Cynthia A. 1 Pokutta, Sebastian 1 Rajan, Deepak 1 Ralphs, Ted K. 1 Salmerón, José M. G. 1 Saltzman, Matthew J. 1 Salvagnin, Domenico 1 Schryen, Guido 1 Sharma, Meenarli 1 Vigerske, Stefan 1 Winkler, Michael 1 Xu, Yan all top 5 Cited in 7 Serials 3 INFORMS Journal on Computing 2 Computational Optimization and Applications 2 Mathematical Programming Computation 1 Computers & Operations Research 1 Journal of Global Optimization 1 European Journal of Operational Research 1 Optimization Methods & Software Cited in 4 Fields 13 Operations research, mathematical programming (90-XX) 5 Numerical analysis (65-XX) 4 Computer science (68-XX) 1 Combinatorics (05-XX) Citations by Year