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: AD BE CF 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: AD BE CF 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: AD BE CF 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