Optimization Online


PEBBL: An Object-Oriented Framework for Scalable Parallel Branch and Bound

Jonathan Eckstein(jeckstei***at***rci.rutgers.edu)
William E. Hart(wehart***at***sandia.gov)
Cynthia A. Phillips(caphill***at***sandia.gov)

Abstract: PEBBL is a C++ class library implementing the underlying operations needed to support a wide variety of branch-and-bound algorithms in a message-passing parallel computing environment. Deriving application-speci c classes from PEBBL, one may create parallel branch-and-bound applications through a process focused on the unique aspects of the application, while relying on PEBBL for generic aspects of branch and bound, such as managing 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, using a distributed-memory programming model and MPI message passing. We describe the basics of PEBBL's architecture and usage, with emphasis on the library's key innovations and contributions, including the notion of branch and bound as a set of operators that manipulate subproblem state transitions. We also describe PEBBL's special features, such as parallel checkpointing, support for specialized ramp-up procedures, and the ability to exhaustively enumerate speci ed sets of near-optimal solutions. Finally, we present an example application, the maximum monomial agreement (MMA) problem arising in machine learning applications. For suciently difficult problem instances, we show essentially linear speedup on over 6,000 processor cores. We also show how processor cache e ects can produce reproducibly superlinear speedups.

Keywords: Branch and bound, combinatorial optimization, parallel computing

Category 1: Optimization Software and Modeling Systems (Parallel Algorithms )

Category 2: Integer Programming (Other )

Citation: RUTCOR Research Report RRR 9-2013, Rutgers University, September 2013.

Download: [PDF]

Entry Submitted: 10/12/2013
Entry Accepted: 10/12/2013
Entry Last Modified: 10/12/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society