Notas

Esquema

Scatter Search and Path Relinking: Methodology and Applications Manuel Laguna

Road to Málaga

SS and PR Publications

SS and PR Bibliography

SS Web Impact

Recent Scatter Search Applications Neural Network Training Multi-Objective Routing Problem OptQuest: A Commercial Implementation A Context-Independent Method for Permutation Problems Classical and Periodic Vehicle Routing Matrix Bandwidth Minimization Arc Crossing Minimization Project Scheduling under Uncertainty P-Median Problems Software Testing DNA Sequencing Network Design Problems in Telecommunications Variable Selection Problems Bus Routing

Scatter Search Seminal ideas originated in the late 60s and first description appeared in … Glover, F. (1977) “Heuristics for Integer Programming Using Surrogate Constraints,” Decision Sciences, vol. 8, pp. 156-166. Modern version of the method is described in … Laguna, M. and R. Martí (2003) Scatter Search: Methodology and Implementations in C, Kluwer Academic Publishers: Boston, ISBN 1-4020-7376-3, 312 pp.

Scatter Search Overview

Reference Set Update Method (Initial RefSet)

Subset Generation Subset Type 1: all 2-element subsets. Subset Type 2: 3-element subsets derived from the 2-element subsets by augmenting each 2-element subset to include the best solution not in this subset. Subset Type 3: 4-element subsets derived from the 3-element subsets by augmenting each 3-element subset to include the best solutions not in this subset. Subset Type 4: the subsets consisting of the best i elements, for i = 5 to b.

Combination Method for Continuous Variables

Alternative Combination Method for Continuous Variables

Variable Number of Solutions

Dynamic RefSet Update Method

Static RefSet Update

2-Tier RefSet

3-Tier RefSet

Rebuilding

GA vs. SS

Parallel Scatter Search (EJOR Special Issue) An empirical investigation on parallelization strategies for Scatter Search B. Adenso-Díaz, S. García-Carvajal, S. Lozano Solving feature subset selection problem by a parallel scatter search F. G. López, M. G. Torres, B. Melián, J. A. Moreno and J. M. Moreno-Vega

Parallel SS of Díaz, et al (2004)

Phase I: Single Walk

Phase I: Multiple Walk/Independent

Phase I: Multiple Walk/Cooperative

Phase II: Single Walk

Phase II: Multiple Walk/Independent Threads

Phase II: Multiple Walks/Cooperative Threads (A)

Phase II: Multiple Walks/Cooperative Threads (B)

Results of Testing 18 Variants Solution Quality Static updating is better than dynamic No interaction effects between phases Phase I MW outperforms SW Cooperation not significantly better Phase II Cooperative variants are superior Execution Time Static updating is faster than dynamic Phase I Cooperative MW Single walk Independent MW Phase II Independent MW Single walk Cooperative MW

Parallel SS of García, et al (2004)

Path Relinking Seminal ideas originated in connection with tabu search … Glover, F. and M. Laguna (1993) “Tabu Search,” in Modern Heuristic Techniques for Combinatorial Problems, C. Reeves (ed.) Blackwell Scientific Publications, pp. 70-150. Modern versions have been applied as a combination method within scatter search and in the improvement phase of GRASP

Path Relinking Research

Relinking Solutions

Multiple Guiding Solutions

Linking Solutions

GRASP (Greedy Randomized Adaptive Search Procedure) Multi-start and local search procedure introduced by Feo and Resende (1989) do { x ß RandomizedGreedyConstruction(a) x ß LocalSearch(x) x* ß UpdateBest(x) } while (termination criterion not met)

GRASP with Path Relinking Originally suggested in the context of Graph Drawing by Laguna and Marti (1999) A guiding solution is selected from a small set (size 3) of elite solutions Initiating solutions are the result of GRASP iterations The number of relinking steps is the number of vertices in the graph Local search is applied every b ~ |E| steps Extensions and comprehensive review are due to Resende and Riberio (2003) “GRASP with Path Relinking: Recent Advances and Applications” http://www.research.att.com/~mgcr/doc/sgrasppr.pdf

Applications three index assignment problem [1, 3] job-shop scheduling problem [1, 2] prize-collecting Steiner tree problem [9] MAX-CUT problem [17] quadratic assignment problem [31] routing private circuits in telecommunication networks [40] p-median problem [43] 2-path network design problem [47] Steiner problem in graphs [49] capacitated minimum spanning tree problem [53]

Relinking Strategies Periodical relinking ¾ not systematically applied to all solutions Forward relinking ¾ worst solution is the initiating solution Backward relinking ¾ best solution is the initiating solution Backward and forward relinking ¾ both directions are explored Mixed relinking ¾ relinking starts at both ends Randomized relinking ¾ stochastic selection of moves Truncated relinking ¾ the guiding solution is not reached

Issues for Future PR Research Selection of initiating and guiding solutions Application of local search to intermediate solutions Testing of standalone PR procedures

Questions