This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Xu, Y. Articles by Saltzman, M. J.

Computational Experience with a Software Framework for Parallel Integer Programming

Operations Research R&D, SAS Institute, Cary, North Carolina 27513
Department of Industrial and Systems Engineering, Lehigh University, Bethlehem, Pennsylvania 18015
Department of Mathematical Sciences, IBM T. J. Watson Research Center, Yorktown Heights, New York 10598
Department of Mathematical Sciences, Clemson University, Clemson, South Carolina 29634
Yan.Xu{at}sas.com
ted{at}lehigh.edu
ladanyi{at}us.ibm.com
mjs{at}clemson.edu

In this paper, we discuss the challenges that arise in parallelizing algorithms for solving generic mixed integer linear programs and introduce a software framework that aims to address these challenges. Although the framework makes few algorithmic assumptions, it was designed specifically with support for implementation of relaxation-based branch-and-bound algorithms in mind. Achieving efficiency for such algorithms is particularly challenging and involves a careful analysis of the trade-offs inherent in the mechanisms for sharing the large amounts of information that can be generated. We present computational results that illustrate the degree to which various sources of parallel overhead affect scalability and discuss why properties of the problem class itself can have a substantial effect on the efficiency of a particular methodology.

Key words: branch and bound; tree search; parallel algorithm; optimization; integer programming; branch and cut
History: received October 2007; revised May 2009; accepted June 2009.