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: | Mitra G., Darby-Dowman K., Nwana V. |
Keywords: | programming: integer, heuristics, computational analysis: parallel computers |
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.