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