Brunel University Research Archive (BURA) >
College of Engineering, Design and Physical Sciences >
Dept of Mathematics >
Dept of Mathematics Research Papers >

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

Title: A co-operative parallel heuristic for integer linear programming: Combining simulated annealing with branch & bound
Authors: Nwana, V
Darby-Dowman, K
Mitra, G
Keywords: Branch and bound
Integer programming
Metaheuristics
Parallel computing
Simulated annealing
Publication Date: 2004
Publisher: Elsevier
Citation: The European Journal of Operational Research (EJOR), 164 (1): 12-23, Jan 2004
Series/Report no.: The Centre for the Analysis of Risk and Optimisation Modelling Applications (CARISMA), Brunel University;Technical Reports
Abstract: This paper considers the exact approach of branch and bound (B&B) and the metaheuristic known as simulated annealing (SA) for processing integer programs (IP). We extend an existing SA implementation (GPSIMAN) for pure zero–one integer programs (PZIP) to process a wider class of IP models, namely mixed zero–one integer programs (MZIP). The extensions are based on depth-first B&B searches at different points within the SA framework. We refer to the resultant SA implementation as MIPSA. Furthermore, we have exploited the use of parallel computers by designing a co-operative parallel heuristic whereby concurrent executions of B&B and MIPSA, linked through a parallel computer, exchange information in order to influence their searches. Results reported for a wide range of models taken from a library of MIP benchmarks demonstrate the effectiveness of using a parallel computing approach which combines B&B with SA.
URI: http://www.elsevier.com/wps/find/journaldescription.cws_home/505543/description#description
http://bura.brunel.ac.uk/handle/2438/702
Appears in Collections:Mathematical Science
Dept of Mathematics Research Papers

Files in This Item:

File Description SizeFormat
sabb.pdf316 kBAdobe PDFView/Open

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