Enhanced Simulated Annealing Through Linear Programming Preprocessing

Publication
Abramson, D., Dang, H. and Krishnamoorthy, M. "Enhanced Simulated Annealing Through Linear Programming Preprocessing", The 12th National Conference of the Australian Society for Operations Research. Adelaide, July 7-9, 1993, pp 91- 114.
Abstract
Simulated annealing (SA) is a heuristic technique which has been successfully applied to a wide range of optimisation problems. Despite its wide applicability, it does have the drawback that the final solution could be suboptimal. Moreover, in problems with the enormous solution spaces, the search for good solutions can be long. In contrast, techniques such as branch and bound provide optimal solutions by systematically pruning the search space with the help of information about the problem. In this paper we describe scheme for combining a relaxed linear program (LP) of a 0-1 optimisation problem with an SA search. This improves the performance of the SA by pruning the search space as it proceeds. Also, the lower bound from the relaxed LP provides a measure of the quality of the SA solution. We are not aware of this approach being used with simulated annealing. We illustrate the technique by applying it to the set partitioning problem (SPP) and give some performance results.
Download
enhanced_annealing.pdf