Optimization Online


Computational Experience with a Software Framework for Parallel Integer Programming

Y. Xu (Yan.Xu***at***sas.com)
T.K. Ralphs (tkralphs***at***lehigh.edu)
L. Ladanyi (ladanyi***at***us.ibm.com)
M.J. Saltzman (mjs***at***clemson.edu)

Abstract: In this paper, we discuss the challenges that arise in parallelizing algorithms for solving mixed integer linear programs and introduce a software framework that aims to address these challenges. The framework 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 tradeoffs 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 demonstrate that properties of the problem class itself can have a substantial effect on the efficiency of a particular methodology.

Keywords: tree search; branch and bound; integer programming; parallel algorithms

Category 1: Optimization Software and Modeling Systems (Parallel Algorithms )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Optimization Software and Modeling Systems (Optimization Software Design Principles )


Download: [PDF]

Entry Submitted: 09/25/2007
Entry Accepted: 09/26/2007
Entry Last Modified: 05/27/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society