







Neural Network Training 

MultiObjective Routing Problem 

OptQuest: A Commercial Implementation 

A ContextIndependent Method for Permutation
Problems 

Classical and Periodic Vehicle Routing 

Matrix Bandwidth Minimization 

Arc Crossing Minimization 

Project Scheduling under Uncertainty 

PMedian Problems 

Software Testing 

DNA Sequencing 

Network Design Problems in Telecommunications 

Variable Selection Problems 

Bus Routing 





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.
156166. 



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 1402073763, 312 pp. 






Subset Type 1: all 2element subsets. 

Subset Type 2: 3element subsets derived from
the 2element subsets by augmenting each 2element subset to include the
best solution not in this subset. 

Subset Type 3: 4element subsets derived from
the 3element subsets by augmenting each 3element 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. 














An empirical investigation on parallelization
strategies for Scatter Search 

B. AdensoDíaz, S. GarcíaCarvajal, 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. MorenoVega 














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 






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. 70150. 



Modern versions have been applied as a
combination method within scatter search and in the improvement phase of
GRASP 









Multistart 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) 





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 




three index assignment problem [1, 3] 

jobshop scheduling problem [1, 2] 

prizecollecting Steiner tree problem [9] 

MAXCUT problem [17] 

quadratic assignment problem [31] 

routing private circuits in telecommunication
networks [40] 

pmedian problem [43] 

2path network design problem [47] 

Steiner problem in graphs [49] 

capacitated minimum spanning tree problem [53] 




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 




Selection of initiating and guiding solutions 



Application of local search to intermediate
solutions 



Testing of standalone PR procedures 

