Please use this identifier to cite or link to this item:
Title: A Two Stage Parallel Branch and Bound Algorithm for Mixed Integer programs
Authors: Nwana, V
Darby-Dowman, K
Mitra, G
Keywords: Branch and bound;Computational behaviour;Heuristics;Integer programming;Parallel computing
Issue Date: 2004
Publisher: Oxford University Press
Citation: This is a pre-copy-editing, author-produced PDF of an article accepted for publication in the IMA Journal of Management Mathematics, following peer review. The definitive publisher-authenticated version IMA Journal of Management Mathematics, Volume 15, Number 3, July 2004, pp. 227-242(16) is available online at:
Series/Report no.: The Centre for the Analysis of Risk and Optimisation Modelling Applications (CARISMA), Brunel University;Technical Reports
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.
Appears in Collections:Dept of Mathematics Research Papers
Mathematical Sciences

Files in This Item:
File Description SizeFormat 
twost.pdf301.04 kBAdobe PDFView/Open

Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.