A co-operative parallel heuristic for mixed zero–one linear programming: Combining simulated annealing with branch and bound

A co-operative parallel heuristic for mixed zero–one linear programming: Combining simulated annealing with branch and bound

0.00 Avg rating0 Votes
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: , ,
Keywords: heuristics, optimization: simulated annealing, programming: branch and bound, programming: linear
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.

Reviews

Required fields are marked *. Your email address will not be published.