XXXV SBPO
Natal, 4-7 de novembro de 2003
A Tabu Search Heuristic for
Partition Coloring with an
Application to Routing and
Wavelength Assignment
Thiago NORONHA
Celso C. RIBEIRO
Novembro 2003
1/29 XXXV SBPO
Tabu search heuristic for partition coloring
Introduction
• The partition coloring problem (PCP)
• Routing and wavelength assignment in alloptical networks (RWA)
• Algorithms for PCP: construction, LS, tabu
search
• Computational results
• Application: static lightpath establishment
• Conclusions
Novembro 2003
2/29 XXXV SBPO
Tabu search heuristic for partition coloring
Partition coloring problem (PCP)
• Graph G = (V,E) with vertex set partitioned into
k disjoint subsets: V = V1  V2  ...  Vp
• PCP consists in coloring exactly one node in
each subset Vi , such that every two adjacent
colored nodes have different colors.
• Objective: minimize the number of colors used.
Novembro 2003
3/29 XXXV SBPO
Tabu search heuristic for partition coloring
Partition coloring problem
1
1
2
1
2
6
0
4
7
2
6
3
4
6
4
0
0
5
2
2
6
3
Novembro 2003
4/29 XXXV SBPO
6
3
Tabu search heuristic for partition coloring
Routing and wavelength assignment in
circuit-switched WDM all-optical
networks
• Different signals can be simultaneously
transmitted in a fiber, using different
wavelengths:
– Wavelength Division Multiplexing
• Connections (between origin-destination
pairs) are established by lightpaths.
• To establish a lightpath consists in
determining:
– a route
Novembro 2003
5/29 XXXV SBPO
Tabu search heuristic for partition coloring
Routing and wavelength assignment in
circuit-switched WDM all-optical
networks
• Each signal can be switched optically at
intermediate nodes in the network.
• No wavelength conversion is possible.
• Lightpaths sharing a common link are not
allowed to use the same wavelength.
• Traffic assumptions: Yoo & Banerjee (1997)
– static lightpath establishment
– dynamic lightpath establishment
(O-D pairs are not known beforehand)
Novembro 2003
6/29 XXXV SBPO
Tabu search heuristic for partition coloring
Routing and wavelength assignment in
circuit-switched WDM all-optical
networks
• Static lightpath establishment (SLE) without
wavelength conversion:
– Minimize the total number of used wavelengths
– Other objective functions may also consider the
load in the most loaded link, the total number of
optical switches (total length), etc.
Novembro 2003
7/29 XXXV SBPO
Tabu search heuristic for partition coloring
Routing and wavelength assignment in
circuit-switched WDM all-optical
networks
Optical network
From SLE to PCP
A
D
h
OXC
B
g
i
OXC
OXC
C
F
AD
CF
gi
gi
gi
BE
Novembro 2003
E
Lightpaths:
AD
BE
CF
8/29 XXXV SBPO
Shortest path routing:
three wavelengths are
needed
Tabu search heuristic for partition coloring
Routing and wavelength assignment in
circuit-switched WDM all-optical
networks
Optical network
From SLE to PCP
A
D
h
OXC
B
g
i
OXC
OXC
C
AD
E
Lightpaths:
AD
BE
CF
F
gi
gi
ghi
BE
ghi
gi
2-shortest path routing
ghi
CF
Novembro 2003
9/29 XXXV SBPO
Tabu search heuristic for partition coloring
Routing and wavelength assignment in
circuit-switched WDM all-optical
networks
Optical network
From SLE to PCP
A
D
h
OXC
B
g
i
OXC
OXC
C
AD
F
gi
gi
ghi
BE
ghi
gi
ghi
CF
Novembro 2003
E
Lightpaths:
AD
BE
CF
10/29 XXXV SBPO
2-shortest path routing:
only two wavelengths are
needed!
Tabu search heuristic for partition coloring
Algorithms for PCP: OnestepCD
(greedy)
1. Remove all edges whose vertices are in same
group.
2. Find the vertex with minimal color-degree for
each uncolored group.
3. Among these vertices, find that with the
largest color-degree.
4. Assign to this vertex the smallest available
color and remove all other vertices in the
same group.
5. Repeat the above steps until all groups are
colored. 11/29 XXXV SBPO
Novembro 2003
Tabu search heuristic for partition coloring
Algorithms for PCP: OnestepCD
• Color degree: number of colored neighbors
Uncolored degree: number of uncolored
neighbors
CD: 0
UD: 3
00
1
2
8
3
7
4
Novembro 2003
CD: 0
UD: 4
12/29 XXXV SBPO
5
6
CD: 01
UD: 20
CD: 01
UD: 20
Tabu search heuristic for partition coloring
Algorithms for PCP: Local search
(1/2)
• First, LS-PCP converts a feasible solution with C
colors into an infeasible solution with C-1 colors;
next, it attempts to restore solution feasibility.
• The local search procedure investigates the
subsets whose colored node is involved in a
coloring conflict.
• LS-PCP searches within each subset for a node
that can be colored or recolored so as to reduce
the overall number of coloring conflicts.
Novembro 2003
13/29 XXXV SBPO
Tabu search heuristic for partition coloring
Algorithms for PCP: Local search
(2/2)
• In case such a node exists, the algorithm moves
to a new solution. Otherwise, another subset is
randomly chosen and investigated.
• If a feasible solution with C-1 colors is found, the
feasibility of this coloring is destroyed and
another coloring using C-2 colors is sought.
• LS-PCP stops when the number of coloring
conflicts cannot be reduced and the solution is
still infeasible.
Novembro 2003
14/29 XXXV SBPO
Tabu search heuristic for partition coloring
Algorithms for PCP: Local search
1
1
0
2
8
3
7
0
4
1
6
5
0
2
8
2
8
3
7
3
7
1
4
5
6
4
2
8
3
7
4
Novembro 2003
0
15/29 XXXV SBPO
5
5
6
Tabu search heuristic for partition coloring
6
Algorithms for PCP: Tabu search
• Simple short-term memory strategy: TS-PCP
• Initial solutions: OnestepCD
• Local search strategy: LS-PCP
– move: pair (node,color)
• Tabu tenure: randomly in U[C/4,3C/4]
• Aspiration criterion: improve best
• Stopping criterion: C.P.10 iterations without
finding a feasible solution, where
C = number of colors and
P = number of subsets in the partition
Novembro 2003
16/29 XXXV SBPO
Tabu search heuristic for partition coloring
Computational results
• Random instances:
– eight PCP instances generated from graph
coloring instances DJSC-250.5 and DJSC-500.5
Aragon, Johnson, McGeoch & C. Schevon (1991)
• nodes in original instance are replicated (2x, 3x, 4x)
• edges are additioned with density 0.5
• one subset for each original node
• Computational experiments: Pentium IV 2.0
GHz
Novembro 2003
17/29 XXXV SBPO
Tabu search heuristic for partition coloring
Computational results
Average results: construction, local search, tabu search
OnestepC
D
Instance
Local search
nodes
colors
colors
DSJC-250.51
250
41.7
DSJC-250.52
DSJC-250.53
500
DSJC-250.54
Novembro 2003
DSJC-500.5-
Tabu search
colors
40.6
%
red.
3
29.6
%
red.
29
40.4
38.1
6
25.8
36
750
38.8
35.6
8
24.0
38
1000
38.3
34.7
9
23.0
40
18/29 XXXV SBPO
500
71.2
35%
Tabu search heuristic for partition coloring
69.3
3
52.6
26
Computational results
Tabu search: solution values and times (10
runs)
Colors
Time (s)
Instance
best
averag
e
worst
to
best
total
DSJC-250.529
29.6
30
6.7
21.4
1
DSJC-250.525
25.8
26
11.7
62.4
Robust!
2
DSJC-250.524
24.0
24
35.2
164.7
3
DSJC-250.523
23.0
23
65.3
300.8
4
DSJC-500.5Novembro 2003
19/29 XXXV
heuristic for partition
52 SBPO 52.6Tabu search53
41.9coloring 197.2
1
Time-to-target-value plots
• Select an instance and a target value:
– 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 computation
time.
• Plots can illustrate algorithm robustness and are
very useful for comparisons based on the
probability distribution of the time-to-targetvalue
20/29 XXXV SBPO
search heuristic for partition coloring
– Aiex, Resende
& RibeiroTabu
(2002)
Novembro 2003
Time-to-target-value plots
Instance DSJC-250.5-4
Novembro 2003
21/29 XXXV SBPO
Tabu search heuristic for partition coloring
Static Lightpath Establishment
• Possible routing algorithms:
– k-shortest paths
– Path stripping: solves LP relaxation and builds
progressively longer shortest routes using edges in
the fractional solution.
Banerjee & Mukherjee (1995)
– Greedy-EDP-RWA: multistart construction using
random permutations (greedy max edge-disjoint
paths routing), too many restarts are needed.
Manohar, Manjunath & Shevgaonkar (2002)
Novembro 2003
22/29 XXXV SBPO
Tabu search heuristic for partition coloring
Application: SLE
• Comparison:
– n-Greedy-EDP-RWA vs. ...
– ... two routing iterations of Greedy-EDP-RWA
followed by partition coloring using TS-PCP
• Both algorithms stop when a target solution
value is found:
– Target is the optimal value of the LP relaxation of
the IP formulation without optical continuity
constraints.
Novembro 2003
23/29 XXXV SBPO
Tabu search heuristic for partition coloring
Application: SLE
SLE instance #1:
14 nodes, 21 links, and 182 connections
Novembro 2003
24/29 XXXV SBPO
Tabu search heuristic for partition coloring
Application: SLE
SLE instance #1: target = 13 (optimal)
Novembro 2003
25/29 XXXV SBPO
Tabu search heuristic for partition coloring
Application: SLE
SLE instance #2:
27 nodes, 70 links, and 702 connections
Novembro 2003
26/29 XXXV SBPO
Tabu search heuristic for partition coloring
Application: SLE
SLE instance #2: target = 24 (optimal)
Novembro 2003
27/29 XXXV SBPO
Tabu search heuristic for partition coloring
Conclusions
• Local search and tabu search heuristic for
partition coloring.
• TS-PCP is able to significantly improve the
solutions obtained by OnestepCD.
• TS-PCP together with a routing algorithm can
be successfully used to solve SLE in RWA.
• Future work will consider other routing
algorithms to be used with TS-PCP to solve
SLE in practical applications.
Novembro 2003
28/29 XXXV SBPO
Tabu search heuristic for partition coloring
Slides and publications
• Slides of this talk can be downloaded from:
http://www.inf.puc-rio/~celso/talks
• Paper will be soon available at:
http://www.inf.pucrio.br/~celso/publicacoes
Novembro 2003
29/29 XXXV SBPO
Tabu search heuristic for partition coloring
Algorithms for PCP: Greedy heuristics
• Onestep Largest First
• Onestep Smallest Last
• Onestep Color Degree (onestepCD)
– best in literature: Li & Simha (2000)
• Twostep Largest First
• Twostep Smallest Last
• Twostep Color Degree
Novembro 2003
30/29 XXXV SBPO
Tabu search heuristic for partition coloring
Computational results
Random instances: varying the number of
subsets
Novembro 2003
31/29 XXXV SBPO
Tabu search heuristic for partition coloring
Computational results
Random instances: varying the graph density
Novembro 2003
32/29 XXXV SBPO
Tabu search heuristic for partition coloring