Massively-Parallel Mixed-Integer Programming: Algorithms and Applications

Cindy Phillips, Sandia National Laboratories

Mixed-integer linear programming (MIP), optimization of a linear function subject to linear and integrality constraints, is a standard technology for efficient allocation of limited resources. I will present applications of MIP to areas such as logistics, site and infrastructure surety, and computational biology.

Mixed-integer programs are typically (approximately) solved in practice by intelligent search based on branch-and-bound and branch-and-cut (constraint generation). We have developed a massively-parallel branch-and-bound environment, applied to MIP, to address national-scale problems. I will describe the design and implementation of this branch-and-bound engine with emphasis on features for scalability, efficiency, and flexibility. I will describe various sources of parallelism in MIP including parallel gradient evalution, parallel bounding, parallel model improvement, and parallel cooperative search.

Created: 9/29/03
Modified: 9/29/03