Deepak Rajan - Distributed-memory branch-and-bound tree search for stochastic Mixed-Integer Programs (MIPs)

Seminar | May 1 | 3:30-5:30 p.m. | 3108 Etcheverry Hall

 Deepak Rajan, University of California Berkeley

 Industrial Engineering & Operations Research

Abstract: In this talk, I present and compare two frameworks for distributed-memory branch-and-bound (B&B) tree search. I'll begin with a brief introduction to Stochastic MIPs and to LP relaxation based Branch-and-Bound for solving MIPs. Both of the frameworks presented in this talk are implemented as extensions of PIPS-SBB, which is already a parallel distributed-memory stochastic MIP solver based on the distributed memory stochastic LP solver PIPS-S. As result, both frameworks include two levels of distributed-memory parallelism, for solving LP relaxations and for B&B tree search. The first framework relies on UG, part of the SCIP project, and implements an external coarse parallelization of PIPS-SBB. The second framework, Parallel PIPS-SBB implements a novel internal fine-grained parallelization of PIPS-SBB. We present computational results that evaluate the effectiveness of both frameworks.

Collaborators: Lluis Munguia, Geoffrey Oxberry, Yuji Shinano

Bio: Deepak Rajan is an Operations Research expert in the Center for Applied Scientific Computing (CASC). His research broadly lies in the areas of computational optimization and integer programming, and more specifically in applying such techniques in solving large-scale problems. Recently, Deepak has been working on optimization problems that involve uncertainty in the energy area (power generation, in particular). He has also worked on a variety of optimization problems in other domains, including network design and graph data mining.

Since 2016, Deepak is also an Associate Adjunct Professor of Industrial Engineering and Operations Research at the University of California at Berkeley., 510-642-6222