Multi-start methods for combinatorial optimization

R. Martí, M.G.C. Resende, and C.C. Ribeiro

European J. of Operational Research, vol. 226, pp. 1-8, 2013


Multi-start methods strategically sample the solution space of an optimization problem. The most successful of these methods have two phases that are alternated for a certain number of global iterations. The first phase generates a solution and the second seeks to improve the outcome. Each global iteration produces a solution that is typically a local optimum, and the best overall solution is the output of the algorithm. The interaction between the two phases creates a balance between search diversification (structural variation) and search intensification (improvement), to yield an effective means for generating high-quality solutions. This survey briefly sketches historical developments that have motivated the field, and then focuses on modern contributions that define the current state-of-the-art. We consider two categories of multi-start methods: memory-based and memoryless procedures. The former are based on identifying and recording specific types of information (attributes) to exploit in future constructions. The latter are based on order statistics of sampling and generate unconnected solutions. An interplay be- tween the features of these two categories provides an inviting area for future exploration.

PDF file of full paper

Go back

Mauricio G.C. Resende's Home Page

Last modified: 02 January 2013

Copyright Notice