PICO: a massively parallel branch-and-bound toolbox
===================================================

Jonathan Eckstein
Department of Management Science and Information Systems
Faculty of Management, Rutgers University
On sabbatical at the ORFE Department, Princeton University

Joint work with Cynthia A. Phillips and William E. Hart,
Sandia National Laboratories.

PICO is a general-purpose, object-oriented toolbox for expressing
branch-and-bound algorithms and executing them in parallel computing
environments.  The initial target architecture is the "Janus"
supercomputer consisting of 4,536 nodes, each with two Pentium-II
processors, although it is designed to be portable and adaptable.
PICO is implemented in C++, using the MPI message passing interface,
and is intended to be scalable to thousands of processors.  Its key
innovations include:

(1) A novel object-oriented approach to describing branch-and-bound
algorithms, permitting many different variants of the method, for
numerous applications, to use the same underlying search "engine".

(2) An architecture whereby applications can first be developed
sequentially using PICO's "serial layer", and then quickly converted
to parallel execution.

(3) A "stride scheduler" that handles multiple asynchronous parallel on
each processing node, and provides a framework for smoothly "blending"
branch and bound with other, heuristic search methods in a parallel
environment.

We will examine a sample application of PICO to general mixed-integer
programming problems, with preliminary computational results on up to
128 processors.