GRASP and Path-Relinking:
Advances and Applications
Celso C. RIBEIRO
September 2003
1/82 CEMAPRE
7th CEMAPRE CONFERENCE
GRASPLisbon,
and path-relinking:
Advances and
applications
September
18-19,
2003
Summary
• The need for heuristics
• Basic GRASP algorithm
• Construction phase
• Enhanced construction strategies
• Local search
• Path-relinking
• GRASP with path-relinking
• Variants of GRASP with path-relinking
• Concluding remarks
... + Applications and numerical results
September 2003
2/82 CEMAPRE
GRASP and path-relinking: Advances and applications
The need for heuristics
• Decision problem: “is there a solution
satisfying some given conditions?”
Answer: “yes” or “no”
• Optimization problem: “among all solutions
satisfying some given conditions, find one
optimizing a cost function.”
Answer: a feasible optimal solution
• Complexity theory: decision problems
September 2003
3/82 CEMAPRE
GRASP and path-relinking: Advances and applications
The need for heuristics
• Example: traveling salesman problem
Input: n cities and distances cij
Decision problem: “given an integer L, is
there a hamiltonian cycle of length less than
or equal to L?”
Optimization problem: “find a minimum
length hamiltonian cycle.”
September 2003
4/82 CEMAPRE
GRASP and path-relinking: Advances and applications
The need for heuristics
• Class P: decision problems solvable by
polynomial time algorithms.
• Examples: shortest paths, minimum spanning
trees, maximum flow, linear programming,
matching, etc.
• Class NP: decision problems for which one
can check in polynomial time if a solution
leads to a “yes” answer (but not necessarilly
find2003one). 5/82 CEMAPRE GRASP and path-relinking: Advances and applications
September
The need for heuristics
• NP-complete problems: hardest decision
problems in NP, if there exists a polynomial
time algorithm for any of them, then all of
them can be solved in polynomial time.
• NP-hard problems: optimization problems
whose associated decision problem is NPcomplete. traveling salesman problem,
• Examples:
knapsack problem, graph coloring, Steiner
problem in graphs, integer programming,
and many others.
September 2003
6/82 CEMAPRE
GRASP and path-relinking: Advances and applications
The need for heuristics
• How do we cope with NP-hardness?
– Heuristics: approximate methods tailored for each
problem, which are able to find high quality feasible
solutions in “reasonable” computation times.
– Strategies:
• Construction algorithms: build feasible solutions
• Local search algorithms: improve feasible solutions and
stop at first local optimum
• Metaheuristics: go beyond local optimality
September 2003
7/82 CEMAPRE
GRASP and path-relinking: Advances and applications
The need for heuristics
• Metaheuristics are based on different
metaphors:
–
–
–
–
–
Simulated annealing
Tabu search
Genetic algorithms
Scatter search
GRASP (greedy randomized adaptive search
procedures)
– Variable neighborhood search
– Ant colonies
– Swarm
particles
September
2003
8/82 CEMAPRE
GRASP and path-relinking: Advances and applications
– Asynchronous teams (A-teams), …
The need for heuristics
• Effective implementation of metaheuristics
combine several common ingredients:
– Greedy algorithms, randomization, local search,
intensification, diversification, short-term
memory, learning, elite solutions, etc.
• Advances in heuristic search methods:
– Solve larger problems
– Solve problems in smaller times
– Find better solutions
September 2003
9/82 CEMAPRE
GRASP and path-relinking: Advances and applications
Summary
•
•
•
•
•
•
•
•
•
The need for heuristics
Basic GRASP algorithm
Construction phase
Enhanced construction strategies
Local search
Path-relinking
GRASP with path-relinking
Variants of GRASP with path-relinking
Concluding remarks
September 2003
10/82 CEMAPRE
GRASP and path-relinking: Advances and applications
GRASP: Basic algorithm
• GRASP:
– Multistart metaheuristic:
• Feo & Resende (1989): set covering
• Festa & Resende (2002): annotated bibliography
• Resende & Ribeiro (2003): survey
• Repeat for Max_Iterations:
– Construct a greedy randomized solution.
– Use local search to improve the constructed solution.
– Update the best solution found.
September 2003
11/82 CEMAPRE
GRASP and path-relinking: Advances and applications
GRASP: Basic algorithm
• Construction phase: greediness + randomness
– Builds a feasible solution:
• Use greediness to build restricted candidate list and
apply randomness to select an element from the list.
• Use randomness to build restricted candidate list and
apply greediness to select an element from the list.
• Local search: search for an improving neighbor
solution until a local optimum is found
– Solutions generated by the construction procedure
are not necessarily optimal:
• Effectiveness of local search depends on neighborhood
structure, search strategy, and fast evaluation of
neighbors, but also on the construction procedure itself.
September 2003
12/82 CEMAPRE
GRASP and path-relinking: Advances and applications
GRASP: Basic algorithm
10.00
local search
9.95
8.00
7.00
weight
phase 2 soln
phase 1 soln
9.00
local search
9.90
weight
10.00
t
)
9.85
phase 2 soln
phase 1 soln
9.80
9.75
9.70
9.65
9.60
GRASP construction
9.55
9.50
0
500
1000 1500 2000
2500
3000 3500 4000 4500
5000
6.00
iterations
5.00
4.00
3.00
2.00
0
500
random construction Effectiveness of greedy randomized vs
purely randomized construction:
Application: modem placement
max weighted covering problem
maximization problem:  = 0.85
iterations
1000
1500
September 2003
2000
2500
3000
3500
4000
13/82 CEMAPRE
GRASP and path-relinking: Advances and applications
Summary
•
•
•
•
•
•
•
•
•
•
The need for heuristics
Basic GRASP algorithm
Construction phase
Enhanced construction strategies
Local search
Path-relinking
GRASP with path-relinking
Variants of GRASP with path-relinking
Parallel implementations
Concluding remarks
September 2003
14/82 CEMAPRE
GRASP and path-relinking: Advances and applications
Construction phase
• Greedy Randomized Construction:
– Solution  
– Evaluate incremental costs of candidate elements
– While Solution is not complete do:
• Build restricted candidate list (RCL).
• Select an element s from RCL at random.
• Solution  Solution  {s}
• Reevaluate the incremental costs.
– endwhile
September 2003
15/82 CEMAPRE
GRASP and path-relinking: Advances and applications
Construction phase
• Minimization problem
• Basic construction procedure:
– Greedy function c(e): incremental cost associated
with the incorporation of element e into the
current partial solution under construction
– cmin (resp. cmax): smallest (resp. largest) incremental
cost
– RCL made up by the elements with the smallest
incremental costs.
September 2003
16/82 CEMAPRE
GRASP and path-relinking: Advances and applications
Construction phase
• Cardinality-based construction:
– p elements with the smallest incremental costs
• Quality-based construction:
– Parameter  defines the quality of the elements in
RCL.
– RCL contains elements with incremental cost
cmin  c(e)  cmin +  (cmax –cmin)
–  = 0 : pure greedy construction
–  = 1 : pure randomized construction
• Select at random from RCL using uniform
probability distribution
September 2003
17/82 CEMAPRE
GRASP and path-relinking: Advances and applications
Illustrative results: RCL parameter
450000
best solution
40
445000
440000
35
435000
average solution
30
solution value
time (seconds) for 1000 iterations
45
430000
25
425000
20
time
420000
15
weighted MAX-SAT
instance: 100 variables and
5
850 clauses
0
1000 GRASP
iterations
0
0.2
0.4
0.6
random
RCL parameter α
415000
10
September 2003
18/82 CEMAPRE
410000
405000
400000
0.8
1
greedy
SGI Challenge 196 MHz
GRASP and path-relinking: Advances and applications
Illustrative results: RCL parameter
20
15
total CPU time
10
5
local search CPU time
Another weighted MAX-SAT instance
0
random
September 2003
0.2
0.4
0.6
0.8
greedy
SGI Challenge 196 MHz
RCL
parameter
α
RCL
parameter
alpha
19/82 CEMAPRE
1
GRASP and path-relinking: Advances and applications
Summary
•
•
•
•
•
•
•
•
•
The need for heuristics
Basic GRASP algorithm
Construction phase
Enhanced construction strategies
Local search
Path-relinking
GRASP with path-relinking
Variants of GRASP with path-relinking
Concluding remarks
September 2003
20/82 CEMAPRE
GRASP and path-relinking: Advances and applications
Enhanced construction strategies
• Reactive GRASP: Prais & Ribeiro (2000) (traffic
assignment in TDMA satellites)
– At each GRASP iteration, a value of the RCL
parameter  is chosen from a discrete set of values
[1, 2, ..., m].
– The probability that k is selected is pk.
– Reactive GRASP: adaptively changes the
probabilities [p1, p2, ..., pm] to favor values of  that
produce good solutions.
– Other applications, e.g. to graph planarization, set
covering, and weighted max-sat:
– Better solutions, at the cost of slightly larger times.
September 2003
21/82 CEMAPRE
GRASP and path-relinking: Advances and applications
Enhanced construction strategies
• Cost perturbations: Canuto, Resende, & Ribeiro
(2001) (prize-collecting Steiner tree)
– Randomly perturb original costs and apply some
heuristic.
– Adds flexibility to algorithm design:
• May be more effective than greedy randomized
construction in circumstances where the construction
algorithm is not very sensitive to randomization.
• Also useful when no greedy algorithm is available.
September 2003
22/82 CEMAPRE
GRASP and path-relinking: Advances and applications
Enhanced construction strategies
• Memory and learning in construction: Fleurent
& Glover (1999) (quadratic assignment)
– Uses long-term memory (pool of elite solutions) to
favor elements which frequently appear in the elite
solutions (consistent and strongly determined
variables).
September 2003
23/82 CEMAPRE
GRASP and path-relinking: Advances and applications
Summary
•
•
•
•
•
•
•
•
•
The need for heuristics
Basic GRASP algorithm
Construction phase
Enhanced construction strategies
Local search
Path-relinking
GRASP with path-relinking
Variants of GRASP with path-relinking
Concluding remarks
September 2003
24/82 CEMAPRE
GRASP and path-relinking: Advances and applications
Local search
• First improving vs. best improving:
– First improving is usually faster.
– Premature convergence to low quality local optimum
is more likely to occur with best improving.
• VND to speedup search and to overcome
optimality w.r.t. to simple neighborhoods:
Ribeiro, Uchoa, & Werneck (2002) (Steiner
problem in graphs)
• Hashing to avoid cycling or repeated application
of local search to same solution built in the
construction phase: Woodruff & Zemel (1993),
Ribeiro et. al (1997) (query optimization),
September 2003
CEMAPRE
GRASP and path-relinking: Advances and applications
Martins et al.25/82(2000)
(Steiner
problem in graphs)
Local search
• Filtering to avoid application of local search to
low quality solutions, only promising solutions
are investigated: Feo, Resende, & Smith (1994),
Prais & Ribeiro (2000) (traffic assignment),
Martins et. al (2000) (Steiner problem in graphs)
• Extended quick-tabu local search to overcome
premature convergence: Souza, Duhamel, &
Ribeiro (2003) (capacitated minimum spanning
tree, better solutions for largest benchmark
problems)
• Candidate list
strategies
September 2003
26/82 CEMAPRE
GRASP and path-relinking: Advances and applications
Summary
•
•
•
•
•
•
•
•
•
The need for heuristics
Basic GRASP algorithm
Construction phase
Enhanced construction strategies
Local search
Path-relinking
GRASP with path-relinking
Variants of GRASP with path-relinking
Concluding remarks
September 2003
27/82 CEMAPRE
GRASP and path-relinking: Advances and applications
Path-relinking
• Path-relinking:
– Intensification strategy exploring trajectories
connecting elite solutions: Glover (1996)
– Originally proposed in the context of tabu search
and scatter search.
– Paths in the solution space leading to other elite
solutions are explored in the search for better
solutions:
• selection of moves that introduce attributes of a
guiding solution into the current solution
September 2003
28/82 CEMAPRE
GRASP and path-relinking: Advances and applications
Path-relinking
• Exploration of trajectories that connect high
quality (elite) solutions:
initial
solution
September 2003
path in the neighborhood of solutions
29/82 CEMAPRE
guiding
solution
GRASP and path-relinking: Advances and applications
Path-relinking
• Path is generated by selecting moves that
introduce in the initial solution attributes of
the guiding solution.
• At each step, all moves that incorporate
attributes of the guiding solution are
evaluated and the best move is selected:
guiding
solution
initial
solution
September 2003
30/82 CEMAPRE
GRASP and path-relinking: Advances and applications
Path-relinking
Elite solutions x and y
(x,y): symmetric difference between x and y
while ( |(x,y)| > 0 ) {
evaluate moves corresponding in (x,y)
make best move
update (x,y)
}
September 2003
31/82 CEMAPRE
GRASP and path-relinking: Advances and applications
Summary
•
•
•
•
•
•
•
•
•
The need for heuristics
Basic GRASP algorithm
Construction phase
Enhanced construction strategies
Local search
Path-relinking
GRASP with path-relinking
Variants of GRASP with path-relinking
Concluding remarks
September 2003
32/82 CEMAPRE
GRASP and path-relinking: Advances and applications
GRASP with path-relinking
• Maintains a set of elite solutions found during
GRASP iterations.
• After each GRASP iteration (construction and
local search):
– Use GRASP solution as initial solution.
– Select an elite solution uniformly at random:
guiding solution (may also be selected with
probabilities proportional to the symmetric
difference w.r.t. the initial solution).
– Perform path-relinking between these two
solutions.
September
2003
33/82 CEMAPRE
GRASP and path-relinking: Advances and applications
GRASP with path-relinking
• Repeat for Max_Iterations:
–
–
–
–
–
Construct a greedy randomized solution.
Use local search to improve the constructed solution.
Apply path-relinking to further improve the solution.
Update the pool of elite solutions.
Update the best solution found.
September 2003
34/82 CEMAPRE
GRASP and path-relinking: Advances and applications
GRASP with path-relinking
• Variants: trade-offs between computation time
and solution quality
– Explore different trajectories (e.g. backward,
forward): better start from the best, neighborhood
of the initial solution is fully explored!
– Explore both trajectories: twice as much the time,
often with marginal improvements only!
– Do not apply PR at every iteration, but instead only
periodically: similar to filtering during local search.
– Truncate the search, do not follow the full
trajectory.
– May also be applied as a post-optimization step to
Septemberall
2003pairs of elite
35/82 CEMAPRE
GRASP and path-relinking: Advances and applications
solutions.
GRASP with path-relinking
•
Successful applications:
1) Prize-collecting minimum Steiner tree problem:
Canuto, Resende, & Ribeiro (2001) (e.g.
improved all solutions found by approximation
algorithm of Goemans & Williamson)
2) Minimum Steiner tree problem:
Ribeiro, Uchoa, & Werneck (2002) (e.g., best
known results for open problems in series dv640
of the SteinLib)
3) p-median: Resende & Werneck (2002) (e.g.,
best known solutions for problems in literature)
September 2003
36/82 CEMAPRE
GRASP and path-relinking: Advances and applications
GRASP with path-relinking
•
Successful applications (cont’d):
4) Capacitated minimum spanning tree:
Souza, Duhamel, & Ribeiro (2002) (e.g., best known
results for largest problems with 160 nodes)
5) 2-path network design: Ribeiro & Rosseti (2002)
(better solutions than greedy heuristic)
6) Max-cut: Festa, Pardalos, Resende, & Ribeiro
(2002) (e.g., best known results for several
instances)
7) Quadratic assignment: Oliveira, Pardalos, &
Resende (2003)
September 2003
37/82 CEMAPRE
GRASP and path-relinking: Advances and applications
GRASP with path-relinking
•
Successful applications (cont’d):
8) Job-shop scheduling: Aiex, Binato, & Resende
(2003)
9) Three-index assignment problem: Aiex, Resende,
Pardalos, & Toraldo (2003)
10) PVC routing: Resende & Ribeiro (2003)
11) Phylogenetic trees: Ribeiro & Vianna (2003)
September 2003
38/82 CEMAPRE
GRASP and path-relinking: Advances and applications
GRASP with path-relinking
• P is a set (pool) of elite solutions.
• Each iteration of first |P| GRASP iterations
adds one solution to P (if different from
others).
• After that: solution x is promoted to P if:
– x is better than best solution in P.
– x is not better than best solution in P, but is
better than worst and is sufficiently different
all solutions
in P.GRASP and path-relinking: Advances and applications
Septemberfrom
2003
39/82 CEMAPRE
Local access network design
• Design a local access network taking into
account tradeoff between:
– cost of network
– revenue potential of network
September 2003
40/82 CEMAPRE
GRASP and path-relinking: Advances and applications
Local access network design
• Build an optical fyber network to provide large
bandwidth services to commercial and
residential users, taking into account the
construction costs (fyber laying) and the
potential revenues obtained by providing the
services to the selected clients (loss of revenue
in the case of clients which are not served).
• Prize-collecting Steiner tree problem:
application developped for AT&T
September 2003
41/82 CEMAPRE
GRASP and path-relinking: Advances and applications
Local access network design
Street
(cost)
September 2003
residence
(revenue)
42/82 CEMAPRE
GRASP and path-relinking: Advances and applications
potential equipment
location (cost)
coverage area of equipment
September 2003
43/82 CEMAPRE
GRASP and path-relinking: Advances and applications
Locate p boxes to maximize revenue of covered residences.
potential equipment
area of coverage
location
September 2003
44/82 CEMAPRE
GRASP and path-relinking: Advances and applications
Assign to each equipment box the total
revenue
of residences it covers for which there
is
equipment
no closer box. This is the prize.
box
September 2003
45/82 CEMAPRE
GRASP and path-relinking: Advances and applications
Solve prize-collecting Steiner tree problem
Maximize prize collected minus edge
costs:
Here all prizes are collected.
September 2003
46/82 CEMAPRE
GRASP and path-relinking: Advances and applications
Solve prize collecting Steiner tree problem
Maximize prize collected minus edge
costs:
Here not all prizes are collected.
September 2003
47/82 CEMAPRE
GRASP and path-relinking: Advances and applications
Prize collecting Steiner tree
problem
• Typical dimension: 20,000 to 100,000
nodes.
• Use GRASP for maximum covering to locate
equipment boxes.
• Compute lower bounds with cutting planes
algorithm of Lucena & Resende (2000).
• Compute solutions (upper bounds) with
GRASP (local search with perturbations)
algorithm
of48/82
Canuto,
Resende,
& Advances
Ribeiro
September
2003
CEMAPRE
GRASP
and path-relinking:
and applications
Prize collecting Steiner tree
problem
• Construction phase (each iteration):
– Memory-based perturbation of original costs to
diversify previously obtained solutions.
– Determine nodes to be collected using Goemans
& Williamson (1996) 2-opt primal-dual
algorithm.
– Connect the selected nodes by a minimum
spanning tree.
• Local search: add/drop nodes to/from the
current tree.
• PR: nodes in one solution but not in the other
September 2003
49/82 CEMAPRE
GRASP and path-relinking: Advances and applications
Prize collecting Steiner tree
problem
• Computational results:
– 114 test problems (up to 1,000 nodes and 25,000
edges)
– Heuristic found:
• 96 out of 104 known optimal solutions.
• Solution within 1% of lower bound for 104 of 114 problems.
– PR more than doubled the number of optima found.
– Cutting plane algorithm produces tight lower bounds
but running times are very high for the largest
instances (days, even weeks), while the GRASP
heuristic
averaged
lessGRASP
than
hours for
the
same
September
2003
50/82 CEMAPRE
and 3
path-relinking:
Advances
and applications
instances.
Summary
•
•
•
•
•
•
•
•
•
The need for heuristics
Basic GRASP algorithm
Construction phase
Enhanced construction strategies
Local search
Path-relinking
GRASP with path-relinking
Variants of GRASP with path-relinking
Concluding remarks
September 2003
51/82 CEMAPRE
GRASP and path-relinking: Advances and applications
Time-to-target-value plots
• Probability distribution of time-to-targetsolution-value:
– Aiex, Resende, & Ribeiro (2002) and Aiex, Binato,
& Resende (2003) have shown experimentally that
for both pure GRASP and GRASP with pathrelinking the time-to-target-solution-value follows
a two-parameter exponential distribution.
– Consequence: linear speedups for independent
parallel implementations
September 2003
52/82 CEMAPRE
GRASP and path-relinking: Advances and applications
Time-to-target-value plots
• Probability distribution of time-to-targetsolution-value: experimental plots
• Select an instance and a target value.
• For each variant of GRASP with path-relinking:
– Perform 200 runs using different seeds.
– Stop when a solution value at least as good as the
target is found.
– For each run, measure the time-to-target-value.
– Plot the probabilities of finding a solution at least
as good as the target value within some
Septembercomputation
2003
53/82time.
CEMAPRE
GRASP and path-relinking: Advances and applications
Time-to-target-value plots
6
1
5
0.8
measured times
4
0.6
0.4
3
2
0.2
1
0
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
time to target solution value (seconds)
0
1
2
3
4
5
6
exponential quantiles
Random variable time-to-target-solution value fits a two-parameter
exponential distribution.
Therefore, one should expect approximate linear speedup in a
straightforward (independent) parallel implementation.
September 2003
54/82 CEMAPRE
GRASP and path-relinking: Advances and applications
Variants of GRASP + PR
• Variants of GRASP with path-relinking:
–
–
–
–
T
S
GRASP: pure GRASP
G+PR(B): GRASP with backward PR
S
G+PR(F): GRASP with forward PR
G+PR(BF): GRASP with two-way PRS
T: elite solution S: local search
• Other strategies:
S
– Truncated path-relinking
– Do not apply PR at every iteration (frequency)
September 2003
55/82 CEMAPRE
T
T
T
GRASP and path-relinking: Advances and applications
2-path network design problem
• 2-path network design problem:
– Graph G=(V,E) with edge weights we and set D of
origin-destination pairs (demands): find a
minimum weighted subset of edges E’  E
containing a 2-path (path with at most two edges)
in G between the extremities of every origindestination pair in D.
• Applications: design of communication
networks, in which paths with few edges are
sought to enforce high reliability and small
September 2003
56/82 CEMAPRE
GRASP and path-relinking: Advances and applications
delays
probability
2-path network design problem
Each variant: 200 runs for one instance of 2PNDP
1.0
0.9
0.8
0.7
0.6
80 nodes,
800 pairs,
target=58
8
0.5
GRASP
G+PR (F)
G+PR (B)
G+PR (BF)
0.4
0.3
Sun Sparc Ultra 1
0.2
0.1
0.0
0.1
September 2003
1
10
100
t ime to t arget v alue (s ec onds )
57/82 CEMAPRE
1000
10000
GRASP and path-relinking: Advances and applications
2-path network design problem
• Same computation time: probability of finding a
solution at least as good as the target value
increases from GRASP  G+PR(F)  G+PR(B) 
G+PR(BF)
• P(h,t) = probability that variant h finds a solution
as good as the target value in time no greater
than t
– P(GRASP,10s) = 2%
P(G+PR(F),10s) = 56%
P(G+PR(B),10s) = 75% P(G+PR(BF),10s) = 84%
September 2003
58/82 CEMAPRE
GRASP and path-relinking: Advances and applications
Variants of GRASP + PR
• More recently:
– G+PR(M): mixed back and forward strategy
T: elite solution S: local search
T
S
– Path-relinking with local search
– Randomized path-relinking
September 2003
59/82 CEMAPRE
GRASP and path-relinking: Advances and applications
probability
2-path network design problem
Each variant: 200 runs for one instance of 2PNDP
1.0
0.9
0.8
0.7
0.6
80 nodes,
800 pairs,
target=58
8
0.5
GRASP
G+PR (F)
G+PR (B)
G+PR (BF)
G+PR (M)
0.4
0.3
0.2
Sun Sparc Ultra 1
0.1
0.0
0.1
September 2003
1
10
100
t ime to t arget v alue (s ec onds )
60/82 CEMAPRE
1000
10000
GRASP and path-relinking: Advances and applications
2-path network design problem
Instance GRASP G+PR(F G+PR(B) G+PR(FB G+PR(M 10 runs,
)
)
)
same
computation
100-3
773
762
756
757
754
100-5
756
742
739
737
728
200-3
1564
1523
1516
1508
1509
200-5
1577
1567
1543
1529
1531
300-3
2448
2381
2339
2356
2338
300-5
2450
2364
2328
2347
2322
400-3
3388
3311
3268
3227
3257
400-5
3416
3335
3267
3270
3259
500-3
4347
4239
4187
4170
4187
500-5
4362
4263
4203
4211
4200
September 2003
61/82 CEMAPRE
time for
each variant,
best solution
found
GRASP and path-relinking: Advances and applications
2-path network design problem
• Effectiveness of G+PR(M):
G+PR(M D&J
) Sample Sample
– 100 small instances with 70
nodes generated as in Dahl
B
A
and Johannessen (2000) for
Size
100
30
comparison purposes.
– Statistical test t for
Mean
443.7
453.7
unpaired observations
(-2.2%)
– GRASP finds better
Std.
40.6
61.6
solutions with 40% of
dev.
confidence (unpaired
observations and manyRibeiro & Rosseti (2002)
optimal
September
2003 solutions):
62/82 CEMAPRE
GRASP and path-relinking: Advances and applications
2-path network design problem
• Effectiveness of path-relinking to improve and
speedup the pure GRASP.
• Strategies using the backwards component are
systematically better.
September 2003
63/82 CEMAPRE
GRASP and path-relinking: Advances and applications
PVC routing
• Frame relay service offers virtual private networks to
customers by providing long-term private virtual
circuits (PVCs) between customer endpoints on a
backbone network.
• Routing is done either automatically by switch or by
the network designer without any knowledge of
future requests.
• Over time, these decisions cause inefficiencies in
the network and occasionally offline rerouting
(grooming) of the PVCs is needed:
– integer multicommodity network flow problem: Resende
& Ribeiro (2003)
September 2003
64/82 CEMAPRE
GRASP and path-relinking: Advances and applications
PVC routing
September 2003
65/82 CEMAPRE
GRASP and path-relinking: Advances and applications
PVC routing
September 2003
66/82 CEMAPRE
GRASP and path-relinking: Advances and applications
PVC routing
September 2003
67/82 CEMAPRE
GRASP and path-relinking: Advances and applications
PVC routing
September 2003
68/82 CEMAPRE
GRASP and path-relinking: Advances and applications
PVC routing
max capacity = 3
September 2003
69/82 CEMAPRE
GRASP and path-relinking: Advances and applications
PVC routing
very long path!
September 2003
70/82 CEMAPRE
max capacity = 3
GRASP and path-relinking: Advances and applications
PVC routing
very long path!
max capacity = 3
reroute
September 2003
71/82 CEMAPRE
GRASP and path-relinking: Advances and applications
PVC routing
max capacity = 3
September 2003
72/82 CEMAPRE
GRASP and path-relinking: Advances and applications
PVC routing
max capacity = 3
feasible and
optimal!
September 2003
73/82 CEMAPRE
GRASP and path-relinking: Advances and applications
PVC routing
Each variant: 200 runs for one instance of PVC routing problem
(60 nodes, 498 edges, 750 origin-destination pairs)
1
G
GPRf
GPRb
GPRf b
0.9
0.8
Probability
0.7
0.6
0.5
0.4
SGI Challenge 196 MHz
0.3
0.2
0.1
0
10
September 2003
100
1000
74/82 CEMAPRE
10000
100000
1e+06
time (seconds)
GRASP and path-relinking: Advances and applications
PVC routing
10 runs
Variant
10 seconds
best
averag
e
100 seconds
best
averag
e
GRASP
126603 126695 126228 126558
G+PR(F)
126301 126578 126083 126229
G+PR(B)
125960 126281 125666 125883
G+PR(BF) 125961 126307 125646 125850
September 2003
75/82 CEMAPRE
GRASP and path-relinking: Advances and applications
PVC routing
10 runs
Variant
10 seconds
best
averag
e
100 seconds
best
averag
e
GRASP
126603 126695 126228 126558
G+PR(F)
126301 126578 126083 126229
G+PR(B)
125960 126281 125666 125883
G+PR(BF) 125961 126307 125646 125850
September 2003
76/82 CEMAPRE
GRASP and path-relinking: Advances and applications
PVC routing
GRASP + PR backwards: four increasingly difficult target values
Same behavior, plots
drift to the right for
more difficult targets
SGI Challenge 196 MHz
September 2003
77/82 CEMAPRE
GRASP and path-relinking: Advances and applications
GRASP with path-relinking
•
Post-optimization “evolutionary” strategy:
a) Start with pool P0 found at end of GRASP and set k
= 0.
b) Combine with path-relinking all pairs of solutions
in Pk.
c) Solutions obtained by combining solutions in Pk are
added to a new pool Pk+1 following same
constraints for updates as before.
d) If best solution of Pk+1 is better than best solution of
Pk, then set k = k + 1, and go back to step (b).
• Succesfully
used
by Ribeiro,
Werneck
September
2003
78/82 CEMAPRE
GRASP and Uchoa,
path-relinking: &
Advances
and applications
(2002) (Steiner) and Resende & Werneck (2002)
Summary
•
•
•
•
•
•
•
•
•
The need for heuristics
Basic GRASP algorithm
Construction phase
Enhanced construction strategies
Local search
Path-relinking
GRASP with path-relinking
Variants of GRASP with path-relinking
Concluding remarks
September 2003
79/82 CEMAPRE
GRASP and path-relinking: Advances and applications
Concluding remarks (1/2)
• Path-relinking adds memory and
intensification mechanisms to GRASP,
systematically contributing to improve
solution quality:
– better solutions in smaller times
– some implementation strategies appear to be
more effective than others).
– mixed path-relinking strategy is very promising
– backward relinking is usually more effective than
forward
– bidirectional relinking does not necessarily pays
the additional computation time
September 2003
80/82 CEMAPRE
GRASP and path-relinking: Advances and applications
Concluding remarks (2/2)
• Difficulties:
– How to deal with infeasibilities along the
relinking procedure?
– How to apply path-relinking in “partitioning”
problems such as graph-coloring, bin packing,
and others?
• Other applications of path-relinking:
– VNS+PR: Festa, Pardalos, Resende, & Ribeiro
(2002)
– PR as a generalized optimized crossover in
genetic algorithms: Ribeiro & Vianna (2003)
• Effective parallel strategies based on pathrelinking
to introduce
memory
and
processor
September
2003
81/82 CEMAPRE
GRASP
and path-relinking:
Advances
and applications
cooperation (robustness and linear speedups).
Slides, publications, and
acknowledgements
• Slides of this talk can be downloaded from:
http://www.inf.puc-rio/~celso/talks
• Papers about GRASP, path-relinking, and their
applications available at:
http://www.inf.puc-rio.br/~celso/publicacoes
• Joint work done mostly with Maurício Resende (AT&T
Labs) and M.Sc. and Ph.D. students from PUC-Rio, who
are all gratefully acknowledged: S. Canuto, M. Souza, M.
Prais, S. Martins, D. Vianna, R. Aiex, R. Werneck, E.
Uchoa, and I. Rosseti.
September 2003
82/82 CEMAPRE
GRASP and path-relinking: Advances and applications