PEBBL: An Object-Oriented Framework for Scalable Parallel Branch and Bound
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-specic 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 specied 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 eects 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.
Entry Submitted: 10/12/2013
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|