Brunel University Research Archive (BURA) >
Schools >
School of Information Systems, Computing and Mathematics >
School of Information Systems, Computing and Mathematics Research Papers >

Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/700

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
Publication 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: http://dx.doi.org/10.1093/imaman/15.3.227
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.
URI: http://bura.brunel.ac.uk/handle/2438/700
Appears in Collections:School of Information Systems, Computing and Mathematics Research Papers
Mathematical Science

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.