A two-stage parallel branch and bound algorithm for mixed integer programs

A two-stage parallel branch and bound algorithm for mixed integer programs

0.00 Avg rating0 Votes
Article ID: iaor2008963
Country: United Kingdom
Volume: 15
Issue: 3
Start Page Number: 227
End Page Number: 242
Publication Date: Jul 2004
Journal: IMA Journal of Management Mathematics (Print)
Authors: , ,
Keywords: programming: integer, heuristics, computational analysis: parallel computers
Abstract:

Mixed integer programming (MIP) models are extensively used to aid strategic and tactical decision making in many business sectors. Solving MIP models is a computationally intensive process and there is a need to develop solution approaches that enable larger models to be solved within acceptable timeframes. In this paper, we describe the implementation of a two-stage parallel branch and bound (PB & B) algorithm for MIP. In stage 1 of the algorithm, a multiple heuristic search is implemented in which a number of alternative search trees are investigated using a forest search in the hope of finding a good solution quickly. In stage 2, the search is reorganized so that the branches of a chosen tree are investigated in parallel. A new heuristic is introduced, based on a best projection criterion, which evaluates alternative B & B trees in order to choose one for investigation in stage 2 of the algorithm. The heuristic also serves as a way of implementing a quality load balancing scheme for stage 2 of the algorithm. The results of experimental investigations are reported for a range of models taken from the MIPLIB library of benchmark problems.

Reviews

Required fields are marked *. Your email address will not be published.