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.

References in zbMATH (referenced in 11 articles , 1 standard article )

Showing results 1 to 11 of 11.
Sorted by year (citations)

  1. Schryen, Guido: Parallel computational optimization in operations research: a new integrative framework, literature review and research directions (2020)
  2. Munguía, Lluís-Miquel; Oxberry, Geoffrey; Rajan, Deepak; Shinano, Yuji: Parallel PIPS-SBB: multi-level parallelism for stochastic mixed-integer programs (2019)
  3. Fischetti, Matteo; Monaci, Michele; Salvagnin, Domenico: SelfSplit parallelization for mixed-integer linear programming (2018)
  4. Knueven, Ben; Ostrowski, Jim; Pokutta, Sebastian: Detecting almost symmetries of graphs (2018)
  5. Shinano, Yuji; Berthold, Timo; Heinz, Stefan: ParaXpress: an experimental extension of the FICO Xpress-Optimizer to solve hard MIPs on supercomputers (2018)
  6. Herrera, Juan F. R.; Salmerón, José M. G.; Hendrix, Eligius M. T.; Asenjo, Rafael; Casado, Leocadio G.: On parallel branch and bound frameworks for global optimization (2017)
  7. Shinano, Yuji; Berthold, Timo; Heinz, Stefan: A first implementation of ParaXpress: combining internal and external parallelization to solve MIPs on supercomputers (2016)
  8. Eckstein, Jonathan; Hart, William E.; Phillips, Cynthia A.: PEBBL: an object-oriented framework for scalable parallel branch and bound (2015)
  9. Eckstein, Jonathan; Goldberg, Noam: An improved branch-and-bound method for maximum monomial agreement (2012)
  10. Evtushenko, Yuri; Posypkin, Mikhail; Sigal, Israel: A framework for parallel large-scale global optimization (2009) ioport
  11. Xu, Yan; Ralphs, Ted K.; Ladányi, László; Saltzman, Matthew J.: Computational experience with a software framework for parallel integer programming (2009)