Article ID: | iaor20061824 |
Country: | Netherlands |
Volume: | 164 |
Issue: | 1 |
Start Page Number: | 12 |
End Page Number: | 23 |
Publication Date: | Jul 2005 |
Journal: | European Journal of Operational Research |
Authors: | Mitra G., Darby-Dowman K., Nwana V. |
Keywords: | heuristics, optimization: simulated annealing, programming: branch and bound, programming: linear |
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.