% Template article for preprint document class `elsart'
% SP 2001/01/05

% Modified 2007/01/09 for CTW 2007
% Please find the original file at http://www.elsevier.com/

\documentclass{ctwart}

% Use the option doublespacing or reviewcopy to obtain double line spacing
% \documentclass[doublespacing]{elsart}

% if you use PostScript figures in your article
% use the graphics package for simple commands
% \usepackage{graphics}
% or use the graphicx package for more complicated commands
% \usepackage{graphicx}
% or use the epsfig package if you prefer to use the old commands
% \usepackage{epsfig}

% The amssymb package provides various useful mathematical symbols
\usepackage{amssymb}

\begin{document}

\begin{frontmatter}

% Title, authors and addresses

% use the thanksref command within \title, \author or \address for footnotes;
% use the corauthref command within \author for corresponding author footnotes;
% use the ead command for the email address,
% and the form \ead[url] for the home page:
% \title{Title\thanksref{label1}}
% \thanks[label1]{}
% \author{Name\corauthref{cor1}\thanksref{label2}}
% \ead{email address}
% \ead[url]{home page}
% \thanks[label2]{}
% \corauth[cor1]{}
% \address{Address\thanksref{label3}}
% \thanks[label3]{}

\title{A branch and bound method \\for a clique partitioning problem}

% use optional labels to link authors explicitly to addresses:
% \author[label1,label2]{}
% \address[label1]{}
% \address[label2]{}

\author[label1]{Ir\`ene Charon,}
\author[label1]{Olivier Hudry,}

\address[label1]{T\'el\'ecom ParisTech \& CNRS - LTCI UMR5141, \\46, rue Barrault, 75634 Paris Cedex 13, France}

\begin{keyword}
% keywords here, in the form: keyword \sep keyword
Branch and bound \sep classification \sep clique partitioning of a graph \sep clustering \sep combinatorial optimization \sep graphs \sep Lagrangean relaxation \sep median equivalence relation \sep R\'egnier's problem \sep Zahn's problem
\end{keyword}

\end{frontmatter}

% main text
\section{Introduction}
\label{}

We consider here the problem of the approximation of $m$ symmetric relations defined on a same finite set $X$ into a so-called {\it median equivalence relation} (see below and \cite{BM}), with in particular two special cases: the one for which the $m$ symmetric relations are equivalence relations (R\'egnier's problem \cite{Regnier}), and the one of the approximation of only one symmetric relation ($m=1$) by an equivalence relation (Zahn's problem \cite{Zahn}). These problems arise for instance from the field of classification or clustering: in this case, $X$ is a set of entities (which can be objects, people, projects, propositions, alternatives, and so on) that we want to gather in subsets of $X$ in such a way that the elements of any such subset can be considered as similar while the objects of different subsets can be considered as dissimilar. Each symmetric relation is associated with a criterion specifying, for any pair $\{x, y\}$ of entities, whether $x$ and $y$ are similar or not. Then we try to find the best compromise between all these criteria. This leads us, in Section \ref{CPP}, to state this problem as a graph theoretical problem, that we call CPP for \textit{clique partitioning problem}. As this problem is NP-hard, we design in Section \ref{BB} a branch and bound algorithm to solve this problem, based on a Lagrangean relaxation method for the evaluation function. 



\section{The clique partitioning problem}
\label{CPP}

The problem that we consider here can be mathematically described as follows. We are given a collection $\Pi = (S_1, S_2, ..., S_m)$ of $m$ symmetric binary relations $S_k$, $1 \leq k \leq m$, all defined on a same finite set $X$ of $n$ elements (R\'egnier's problem \cite{Regnier} corresponds to the case for which all the relations $S_k$ are equi\-va\-lence relations; Zahn's problem \cite{Zahn} corresponds to the case for which $m$ is equal to 1). We consider the number $\delta(R, S)$ of disagreements bet\-ween two binary relations $R$ and $S$:
$$\delta(R,S)= |\{(i,j)\in X^{2} \mbox{ with } [iRj \mbox{ and not } iSj] \mbox { or } [iSj \mbox { and not } iRj] \} |.$$
Then, for any equivalence relation $E$, we consider the {\it remoteness} $\Delta(\Pi, E) = \sum_{k=1}^m \delta(S_k, E)$, measuring the total number of disagreements between $\Pi$ and $E$. Our problem thus consists in computing an equivalence relation $E^*$, called a {\it median equivalence relation} of $\Pi$, which minimizes $\Delta$ over the set $\mathcal E$ of all the equivalence relations defined on $X$:
$$\Delta(\Pi, E^*)= \min_{E \in \mathcal E} \Delta(\Pi, E).$$
The computation of $E^*$ is NP-hard \cite{Waka}, and remains so even for R\'egnier's problem or for Zahn's problem.

To state this problem as a 0-1 linear programming problem, let $s^k = (s^k_{ij})_{(i,j) \in X^2}$ ($1 \leq k \leq m$) be the binary vector defined by: $s^k_{ij}=1$ if $iS_kj$ (i.e. if $i$ and $j$ are put together by $S_k$), and $s^k_{ij}=0$ otherwise. Similarly, let $(x_{ij})_{(i,j) \in X^2}$ denote the vector associated with $E$: $x_{ij}=1$ if $iEj$, $x_{ij}=0$ otherwise. It is easy to obtain the following:
$$\delta(S_k, E) = \sum_{(i,j)\in X^2}|s_{ij}^{k}-x_{ij}| = \sum_{(i,j)\in X^2}(s_{ij}^{k}-x_{ij})^2 = \sum_{(i,j)\in X^2}(s_{ij}^k + (1-2s_{ij}^k)x_{ij})$$
because of the binary property of the quantities $s_{ij}^k$ and $x_{ij}$. Then we obtain, for the remoteness:
$$\Delta(\Pi, E) = \sum_{k=1}^m\sum_{(i,j)\in X^2}s_{ij}^k + \sum_{k=1}^m\sum_{(i,j)\in X^2}(1-2s_{ij}^k)x_{ij}= C + \sum_{(i,j)\in X^2}w_{ij}x_{ij}$$
where $C = \sum_{k=1}^m\sum_{(i,j)\in X^2}s_{ij}^k$ is a constant and with, for $(i,j)\in X^2$:
$$w_{ij} = \sum_{k=1}^m(1-2s_{ij}^k)=m-2|\{k \mbox{ with } 1\leq k\leq m\ \mbox{ and } \ iS_kj\}|.$$
So, minimizing $\Delta(\Pi, E)$ is the same as minimizing $\sum_{(i,j)\in X^2}w_{ij}x_{ij}$. Moreover, the constraints to state that $E$ must belong to $\mathcal E$ are the following:
\begin{itemize}
\item symmetry: $\forall (i,j) \in X^2, x_{ij}=x_{ji}$;
\item transitivity: $\forall (i, j, h) \in X^3 \mbox{ with } i \neq j \neq h \neq i, x_{ij} + x_{jh} - x_{ih} \leq 1$.
\end{itemize}
If we add the binary constraints: $\forall (i,j) \in X^2, x_{ij} \in \{0, 1\}$, we obtain our 0-1 linear programming problem.

We now may state this problem as a graph theoretic one. For this, we associate the complete graph $K_n$ to $\Pi$, and we weight every edge $\{i,j\}$ of $K_n$ by $w_{ij}$. Then the variables $x_{ij}$ equal to 1 define cliques (i.e. complete subgraphs) of $K_n$, and the value of $\Delta(\Pi, E)$ is equal to the sum of the weights of the edges with both extremities inside a same clique. Hence our clique partitioning problem CPP. Note that the weights of the edges can be non-positive or non-negative integers. Moreover, the number of cliques into which we want to partition $K_n$ is not given. Finally, CPP can be stated as follows: given a complete graph $K_n = (X, A)$ whose edges $\{i,j\}$ are weighted by non-positive or non-negative integers $w_{ij}$, partition $X$ into $p$ subsets $X_1$, $X_2$, ..., $X_p$, where $p$ is not given, so that $\sum_{h=1}^p \sum_{(i,j)\in (X_h)^2}w_{ij}$ (i.e. the sum of the weights of the edges inside the cliques) is minimum. 


\section{The branch and bound method}
\label{BB}

To solve CPP, we design a branch and bound method BB. We briefly depict the main ingredients of BB. 

The initial bound is provided by a metaheuristic, namely the {\it noising methods} \cite{NM2}, \cite{NM3}. The noising methods usually compute very good solutions, quite often optimal, though we cannot know whether these solutions are indeed optimal.

The BB-tree is built as follows. The vertices $v_i$ of $K_n$ are integers belonging to $\{1, 2, ..., n\}$. A partition with $p$ subsets $X_1$, $X_2$, ..., $X_p$ is represented as:
$$\underbrace{v_1,v_2,..., v_{q_1}}_{X_1}|\underbrace{v_{q_1+1},v_{q_1+2}, ..., v_{q_2}}_{X_2}
       |... |\underbrace{v_{q_{p-1}+1},v_{q_{p-1}+2}, ..., v_{q_p}}_{X_p}$$
With such an encoding, a partition admits several representations. To avoid this, we suppose that the vertices are ordered by increasing value within a subset and subsets are ordered according to their smallest vertices; with the above notation, it means that we have: $1=v_1< v_2 < ...< v_{q_1}$,  $v_{q_1+1}<v_{q_1+2}< ... < v_{q_2}$, ..., $v_{q_{p-1}+1}<v_{q_{p-1}+2}< ... < v_{q_p}$, and $v_1 <v_{q_1+1} < ... <v_{q_{p-1}+1}$. 
       
The subsets are progressively constructed. A node $N$ of the BB-tree corres\-ponds to the beginning of a partition encoding, something like:
$$\underbrace{v_1,v_2,..., v_{q_1}}_{X_1}|\underbrace{v_{q_1+1},v_{q_1+2}, ..., v_{q_2}}_{X_2}
       |... |\underbrace{v_{q_{h-1}+1},v_{q_{h-1}+2}, ..., v_{q_{h-1}+t}}_{X_h}$$
We extend $N$ by at most $n-q_{h-1}-t+1$ new branches. The first branch is obtained by closing the current subset $X_h$ and by creating a new subset $X_{h+1}$ which will contain at least $v_{q_{h-1}+t+1}$. The other branches correspond with the possibilities to expand the current class $X_h$ by adding an extra vertex (greater than $v_{q_{h-1}+t}$) to it: $v_{q_{h-1}+t+1}$, or $v_{q_{h-1}+t+2}$ but not $v_{q_{h-1}+t+1}$, or $v_{q_{h-1}+t+3}$ but neither $v_{q_{h-1}+t+1}$ nor $v_{q_{h-1}+t+2}$, and so on...

Three evaluation functions $F_1$, $F_2$, $F_3$ are designed to evaluate the quality of every node $N$ of the BB-tree. They can be split into two parts. The first part is the same for the three functions: it takes into account the contribution of the vertices already dispatched inside the subsets of the partition under construction associated with $N$; for this, we only sum the weights of the edges with both extremities in a same subset. The second part depends on the function. For $F_1$, we add all the negative weights of the edges with at least one extremity greater than $v_{q_{h-1}+t}$. In $F_2$, we sharpen the design of $F_1$ by considering some triples of vertices (triangles) $\{a,b,c\}$ and by noting that if the weights of the edges between $a$, $b$ and $c$ have not the same sign, then the contribution of $\{a,b,c\}$ cannot be the sum of the negative edges, as in $F_1$; we design a greedy algorithm to choose these triangles in order to improve $F_1$ as much as possible. The last function, $F_3$, is the most sophisticated. It is based on the Lagrangean relaxation of the transitivity constraints (see above).

Other ingredients, not described here, allow us also to cut branches of the BB-tree. During the talk, we will discuss the efficiency of the evaluation functions and of the other ingredients, based on experiments dealing with different kinds of graphs: instances of R\'egnier's problem or of Zahn's problem, instances coming from the literature, random instances, or instances with special combinatorial or algorithmic properties.
 

\begin{thebibliography}{00}
%\bibitem{BL}
%J.-P. Barth\'elemy, B. Leclerc: The median procedure for partitions, in Partitioning data sets, I.J. Cox, P. Hansen, B. Julesz (eds), DIMACS Series in Discrete Mathematics and Theoretical Computer Science 19, Amer. Math. Soc., Providence, RI, 1995, 3-34.

\bibitem{BM}
J.-P. Barth\'elemy, B. Monjardet: The median procedure in cluster analysis and social choice theory, Mathematical Social Sciences 1, 1981, 235-267.

%\bibitem{NM1}
%I. Charon, O. Hudry: The noising methods: a generalization of some metaheuristics, European Journal of Operational Research 135 (1), 2001, 86-101.

\bibitem{NM2}
I. Charon, O. Hudry: Noising methods for a clique partitioning problem, Discrete Applied Mathematics 154 (5), 2006, 754-769.

\bibitem{NM3}
I. Charon, O. Hudry: Self-tuning of the noising methods, Optimization 58 (7), 2009, 1-21.

%\bibitem{KM}
%M. Krivanek, J. Moravek: NP-hard problems in hierarchical-tree clustering, Acta Informatica 23, 1986, 311-323.

\bibitem{Regnier}
S. R\'egnier: Sur quelques aspects math\'ematiques des probl\`emes de classification automatique, I.C.C. Bulletin 4, Rome, 1965.

\bibitem{Waka}
Y. Wakabayashi: The Complexity of Computing Medians of Relations, Resenhas, 3 (3), 1998, 323-349.

\bibitem{Zahn}
C.T. Zahn: Approximating symmetric relations by equivalence relations, SIAM Journal on Applied Mathematics, 12, 1964, 840-847.



\end{thebibliography}

\end{document}


	We denote by $n$ the number of objects. We associate an integer from 1 to $n$ to each of the objects. We define a $n \times n$ symmetric matrix $w$; for $i$ and $j$ between 1 and $n$, $w(i, j)$ is an integer positive or negative; $w(i, j)$ gives the dissimilarity between the objects $i$ and $j$, a negative value indicates that the objects are rather similar; we say that $w(i, j)$ is the weight of the edge $\{i, j\}$. We define a complete non oriented valuated graph $G$ which vertices are the $n$ objects and the valuations on an edge $\{i, j\}$, for $i \neq j$ is equal to $w(i, j)$; we set, for $i$ between 1 and $n$, $w(i, i) = 0$. A  symmetric binary relation $\mathcal{R}$ on the $n$ objects is represented by a triangular matrix $x$ defined for  $1 \leq i < j \leq n$ by: $x(i, j) = 1$ if $i \mathcal{R} j$ and $x(i, j) = 0$ if not. A binary relation is an equivalence relation if and only if (see ???], for $1 \leq i < j < k <\leq n$ 
	
         $$\left\{ \begin{array}{l}
           x_{ik}+x_{jk}-x_{ij}-1\leq 0  \\
           x_{ik}-x_{jk}+x_{ij}-1\leq 0  \\
           -x_{ik}+x_{jk}+x_{ij}-1\leq 0  \\
         \end{array} \right.$$
      
	So, the clique partitioning problem is:
	   $$ \mathcal{P} = \begin{array}{l}
	      	\text{Minimize } f(x) = \sum_{i = 1}^{n-1}\sum_{j=i+1}^{n} x_{ij} w_{ij}\\
	      	\left\{\begin{array}{llll}
           \text{with} & \text{for } 1 \leq i < j < k\leq n \text{, } &x_{ik}+x_{jk}-x_{ij}-1\leq 0  \\
            & \text{for } 1 \leq i < j < k\leq n \text{, }&x_{ik}-x_{jk}+x_{ij}-1\leq 0  \\
            & \text{for } 1 \leq i < j < k \leq n \text{, }&-x_{ik}+x_{jk}+x_{ij}-1\leq 0  \\
           \text{and} &  \text{for } 1 \leq i < j \leq n \text{,} &x_{ij} \in \{0, 1\}\\
         \end{array} \right. \end{array}$$
	
	So, the problem is a linear programming problem in variables 0 or 1.



%\bibitem{Banerjee} D. Banerjee, B. Mukherjee:
%A practical approach for Routing and
%Wavelength Assignment in Large Wavelength-Routed Optical Networks.
%IEEE Journal on Selected Areas in Communications, 14 (5), 903--908, 1996.
\bibitem{Lucile}
L. Belgacem, I. Charon, O. Hudry:
A post-optimization method for the routing and wavelength assignment problem. 
Submitted for publication
\bibitem{Belgacem}
L. Belgacem, N. Puech:
Solving Large Size Instances of the RWA Problem Using Graph Partitioning.
Proceedings of the 12th Conference on Optical Network Design and Modelling, Vilanova i la Geltrú, Spain, 1--6, 2008.
\bibitem{Chlamtac}
I. Chlamtac, A. Ganz, G. Karmi:
Lightpath communications: an approach to high-bandwidth optical WANs.
IEEE Trans. Commun. 40, 1171--1182, 1992.
%\bibitem{Choi}
%J.S. Choi, N. Golmie, F. Lapeyere, F. Mouveaux, D. Su: 
%A functional classification of routing and wavelength assignment schemes in DWDM networks: static case.
%Proc. VII Int. Conf. on Optical Communication and Networks, 2000.

%\bibitem{Chu} X. Chu, B. Li and I. Chlamtac: On the wavelength converter placement for different RWA algorithms in wavelength-routed all-optical networks.
%Proc. SPIE Vol. 4874, p. 186-197, OptiComm 2002: Optical Networking and Communications, Nasir Ghani; Krishna M. Sivalingam; Eds, 2002. 

%\bibitem{GiAhn} 
%H. Gi Ahn, T.-J. Lee, M. Y. Chung, H. Choo: RWA on Scheduled Lightpath Demands in WDM Optical Transport Networks with Time Disjoint Paths, Proc. International Conference on Information Networking, 342-351, 2005.
\bibitem{Kuri} 
J. Kuri, N. Puech, M. Gagnaire, E. Dotaro, R. Douville: Routing and Wavelength Assignment of Scheduled Lightpaths Demands, IEEE Journal on Selected Areas in Communications 21 (8), 1231--1240, 2003.
%\bibitem{Park} 
%S. Park, J. S. Yang, Y.-C. Bang, On RWA Algorithms for Scheduled Lightpath Demands, International Journal of Computer Science and Network Security 7 (3), 144-150, 2007.
%\bibitem{Ramaswami} R. Ramaswami, K.N. Sivarajan:
%Routing and Wavelength Assignment in All-Optical Networks.
%IEEE/ACM Transactions on networking 3 (5), 489--500, 1995.
%\bibitem{Saradhi} 
%C. V. Saradhi, M. Gurusamy, Graph Theoretic Approaches for Routing and Wavelength Assignment of Scheduled Lightpath Demands in WDM Optical  Networks, Proc. 2nd International Conference on Broadband Networks 2, 2005.
\bibitem{Nina06}
N. Skorin-Kapov:
Heuristic Algorithms for the Routing and Wavelength Assignment of Scheduled Lightpath Demands in Optical Networks.
IEEE Journal on Selected Areas in Communications 24 (8), 2-15, 2006.
%\bibitem{Zang}
%H. Zang, J.P. Jue, B. Mukherjee:
%A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks.
%SPIE Optical Networks Magazine 1 (1), 47--60, 2000.




One problem arising from classification 
consists to in uncovering natural groupings
 of objects, each of which is characterized by several attributes.
 These objects can be considered to be the
 vertices of a weighted complete graph 
$G$.
Each positive or negative weight of an edge $\{x,y\}$ 
represents a measure of 
similarity or dissimilarity between the two vertices $x$ and $y$
linked by this edge.
A clustering of the objects into groups or clusters is a partition
of the vertices of the graph $G$ into cliques (non-overlapping subsets),
such that the sum of the weights of all the edges with both extremities in
the same subset (clique) is minimimum.

Several exact or approximate methods
were proposed, for example, an exact algorithms based on branch-and-bound 
 by \cite{TU83} or on polyhedral theory by\cite{GW89} (see also \cite{GW90a}
 and \cite{GW90b}).
To have a complete survey of the partition problem and their integer
programming formulations, 
see \cite{CR93}, \cite{BM81}, \cite{BM88}, \cite{BL95} and \cite{H75}.
\cite{MM80a} proposed a method using
 the dual of the linear programming relaxation of the partitioning 
problem formulated as a 0-1 integer programming problem.
More recently, \cite{DP94} interested themselves in the resolution
by a method of branch-and-bound ; in the same way 
\cite{PA97} describes such a technique using polyhedral results.
The first heuristic for the clustering problem has been developed by Régnier
in 1965 \cite{R65}, new edition \cite{R83}.
 \cite{ARB92} studied tabu search and simulated annealing for this problem.



We consider two problems related to the {\it routing and wavelength assignment problem} (RWA) in  {\it wavelength division multiplexing (WDM) optical networks}. For a given network topology, represented by an undirected graph $\mathcal G$, the RWA problem consists in establi\-shing a set of traffic demands (or connection requests) in this network. Traffic demands may be of three types: static (permanent and known in advance), sche\-duled (requested for a given period of time) and dynamic (unexpected). In this communication, we deal with the case of {\it scheduled lightpaths demands} (SLDs), which is relevant because of the predictable and periodic nature of the traffic load in real transport networks (more intense during working hours, see \cite{Kuri}). 

An SLD can be represented by a quadruplet $s=(x,y,\alpha, \beta)$, where $x$ and $y$ are some vertices of $\mathcal G$ (source and destination nodes of the connection request), and where $\alpha$ and $\beta$ denote the set-up and tear-down dates of the demand. The routing of $s=(x,y,\alpha, \beta)$ consists in setting up a lightpath between $x$ and $y$, i.e. a path between $x$ and $y$ in $\mathcal G$ and a wavelength $w$. In order to satisfy the SLD $s$, this lightpath must be reserved during all the span of $[\alpha, \beta]$. 

The same wavelength must be used on all the links travelled by a lightpath ({\it wavelength continuity constraint}). Moreover, at any given time, a wavelength can be used at most once on a given link; in other words, if two demands overlap in time, they can be assigned the same wavelength if and only if their routing paths are disjoint in edges ({\it wavelength clash constraint}).

The two problems that we consider here are the following:
\begin{itemize}
\item minimize the number of wavelengths necessary to satisfy all the demands;
\item given a number of wavelengths, maximize the number of connection demands that can be satisfied with this number of wavelengths.
\end{itemize}

These problems are NP-hard (see \cite{Chlamtac}), and have been extensively studied (see, among others, \cite{Lucile}, \cite{Belgacem}, \cite{Kuri}, \cite{Nina06} and the reference therein). In both problems, a solution is defined by specifying, for each SLD, the lightpath chosen for supporting the connection (i.e. a path and a wavelength), so that there is no conflict between any two lightpaths (let us recall that two lightpaths are in conflict if they use the same wavelength, they have at least one edge in common and the corresponding demands overlap in time). To solve these problems, we design a modelisation of the problem as the search of successive independent sets (IS) in some conflict graphs. Then we apply a descent heuristic improved by a post-optimization method. 


\section{Independent sets in conflict graphs}

To solve these problems, we build a {\it conflict graph} $\mathcal H$ defined as follows. For each SLD $s = (x, y, \alpha, \beta)$, we compute a given number $k$ of paths between $x$ and $y$ in $\mathcal G$ (for instance, $k=5$): $C^1_s, C^2_s, ..., C^k_s$. We associate a vertex of $\mathcal H$ with each path $C^i_s$ for each SLD $s$. Thus, if $\delta$ denotes the number of SLDs, the number of vertices of $\mathcal H$ is equal to $k \delta$. The edges of $\mathcal H$ are of two types:
\begin{itemize}
\item for each SLD $s$ and for $1 \leq i < j \leq k$, all the edges $\{C^i_s, C^j_s\}$ are in $\mathcal H$; thus these edges induce, for each SLD $s$, a clique (i.e., a complete graph) on the vertices $C^1_s, C^2_s, ..., C^k_s$;
\item for any SLD $s = (x, y, \alpha, \beta)$ and any other SLD $s' = (z, t, \gamma, \epsilon)$, we add the edges $\{C^i_s, C^j_{s'}\}$ for $1 \leq i \leq k$ and $1 \leq j \leq k$ if the time windows of $s$ and $s'$ overlap ($[\alpha, \beta] \cap [\gamma, \epsilon) \neq \emptyset$) and if the paths $C^i_s$ and $C^j_{s'}$ are not edge-disjoint; such an edge $\{C^i_s, C^j_{s'}\}$ represents a conflict between $s$ and $s'$: it is not possible to assign a same wavelength to $s$ and $s'$ if we decide to route $s$ thanks to $C^i_s$ and $s'$ thanks to $C^j_{s'}$.
\end{itemize}

Our algorithm consists in applying the following two steps successively:
\begin{itemize}
\item compute an independent set $I$ in $\mathcal H$;
\item remove from $\mathcal H$ all the cliques associated with the satisfied SLDs to obtain a new current conflict graph $\mathcal H$.
\end{itemize}
We perform this process in order to obtain a series of ISs $I_1$, $I_2$, ..., $I_q$ in successive conflict graphs. This will provide a solution to our problem. Indeed, if the vertex $C^i_s$ belongs to $I_j$, then we route $s$ thanks to the path $C^i_s$ with the $j$-th wavelength. Each $I_j$ allows us to route $|I_j|$ SLDs with a same wavelength. We stop when all the SLDs are satisfied (first problem) or when $q$ is equal to the prescribed number of wavelengths (second problem).

\section{The heuristic to compute an independent set}

To compute an IS in the current conflict graph $\mathcal H$, we apply an {\it iterative improvement method}, also called {\it descent} (we tried more sophisticated methods as simulated annealing, but these methods were too long to obtain interesting results). We start from an IS of cardinality 1, and we look for another IS of cardinality 2, 3, and so on, until reaching a value $\lambda$ for which we do not succeed in finding an IS of cardinality $\lambda$. Then the method returns the last IS of cardinality $\lambda - 1$ as a solution. 

To look for an IS $I_{\lambda}$ of cardinality $\lambda$ from an IS $I_{\lambda - 1}$ of cardinality $\lambda - 1$, we add a random vertex to $I_{\lambda - 1}$. Usually, we thus obtain a set $I_{\lambda}$ inducing a subgraph containing some edges. Then we try to minimize the number of edges by performing elementary (or local) transformations, in order to find a set $I_{\lambda}$ which will be an IS. It is for this minimization that we apply a descent.

The elementary transformation that we adopt consists in removing a vertex belonging to $I_{\lambda}$ and simultaneously to add another vertex which does not belong to $I_{\lambda}$. Such a transformation is indeed accepted if the number of edges decreases.

When the descent stops, if the set $I_{\lambda}$ still induces a subgraph which is not an IS, then we stop and we keep the previous IS $I_{\lambda - 1}$ as the solution. Otherwise, we add a vertex and we apply the same process once again.

In fact, we improve this method in two manners. The first one consists, after the construction of each IS $I$, in trying to add extra SLDs with a greedy algorithm. For this, we consider each unsatisfied SLD $s$, and we look for a path in $\mathcal G$ that would allow us to route $s$ with the current wavelength, i.e. a path which would  not contain any edge of paths associated with another SLD $s'$ routed with the same wavelength and of which the time window overlaps the one of $s$. Such a situation may occur since we limit ourselves to $k$ paths in the construction of $\mathcal H$, while we look for a path in $\mathcal G$ to add extra SLDs.

The other improvement consists in applying a post-optimization method (already applied in \cite{Lucile}), after the computation of the series of ISs $I_1$, $I_2$, ..., $I_q$. The aim is to reduce the overall values of the wavelengths in order to decrease the total number of wavelengths for the first problem or to make some place to extra SLDs, still unsatisfied, for the second problem. For this, given a wavelength $w$, we try to empty, at least partially, the set of SLDs routed with $w$, by assigning them lower wavelengths. So we change the wavelengths assigned to SLDs which are currently routed with the wavelenths $1, 2, ..., w - 1$; in this process, all the SLDs with a current wavelength between $1, 2, ..., w - 1$ will keep a wavelength in this interval. For the first problem, it may then happen that a wavelength becomes useless; then we remove it definitively and so the number of required wavelengths decreases. For the second problem, the changes involved in the assignments of the wavelenghts are such that, sometimes, we may route an SLD which was unsatisfied; so this process allows us to route extra SLDs.



\section{Results}

We experimentally study the impact of the formulation of the problem as the search of successive ISs in conflict graphs as well as the impact of the post-optimization method. The experiments are done on several networks, with numbers of SLDs up to 3000. The results, not detailed here, show that these two approaches are quite beneficial for both problems, when their results are compared to the one of the method developped in \cite{Nina06}.




\begin{thebibliography}{00}

%\bibitem{Banerjee} D. Banerjee, B. Mukherjee:
%A practical approach for Routing and
%Wavelength Assignment in Large Wavelength-Routed Optical Networks.
%IEEE Journal on Selected Areas in Communications, 14 (5), 903--908, 1996.
\bibitem{Lucile}
L. Belgacem, I. Charon, O. Hudry:
A post-optimization method for the routing and wavelength assignment problem. 
Submitted for publication
\bibitem{Belgacem}
L. Belgacem, N. Puech:
Solving Large Size Instances of the RWA Problem Using Graph Partitioning.
Proceedings of the 12th Conference on Optical Network Design and Modelling, Vilanova i la Geltrú, Spain, 1--6, 2008.
\bibitem{Chlamtac}
I. Chlamtac, A. Ganz, G. Karmi:
Lightpath communications: an approach to high-bandwidth optical WANs.
IEEE Trans. Commun. 40, 1171--1182, 1992.
%\bibitem{Choi}
%J.S. Choi, N. Golmie, F. Lapeyere, F. Mouveaux, D. Su: 
%A functional classification of routing and wavelength assignment schemes in DWDM networks: static case.
%Proc. VII Int. Conf. on Optical Communication and Networks, 2000.

%\bibitem{Chu} X. Chu, B. Li and I. Chlamtac: On the wavelength converter placement for different RWA algorithms in wavelength-routed all-optical networks.
%Proc. SPIE Vol. 4874, p. 186-197, OptiComm 2002: Optical Networking and Communications, Nasir Ghani; Krishna M. Sivalingam; Eds, 2002. 

%\bibitem{GiAhn} 
%H. Gi Ahn, T.-J. Lee, M. Y. Chung, H. Choo: RWA on Scheduled Lightpath Demands in WDM Optical Transport Networks with Time Disjoint Paths, Proc. International Conference on Information Networking, 342-351, 2005.
\bibitem{Kuri} 
J. Kuri, N. Puech, M. Gagnaire, E. Dotaro, R. Douville: Routing and Wavelength Assignment of Scheduled Lightpaths Demands, IEEE Journal on Selected Areas in Communications 21 (8), 1231--1240, 2003.
%\bibitem{Park} 
%S. Park, J. S. Yang, Y.-C. Bang, On RWA Algorithms for Scheduled Lightpath Demands, International Journal of Computer Science and Network Security 7 (3), 144-150, 2007.
%\bibitem{Ramaswami} R. Ramaswami, K.N. Sivarajan:
%Routing and Wavelength Assignment in All-Optical Networks.
%IEEE/ACM Transactions on networking 3 (5), 489--500, 1995.
%\bibitem{Saradhi} 
%C. V. Saradhi, M. Gurusamy, Graph Theoretic Approaches for Routing and Wavelength Assignment of Scheduled Lightpath Demands in WDM Optical  Networks, Proc. 2nd International Conference on Broadband Networks 2, 2005.
\bibitem{Nina06}
N. Skorin-Kapov:
Heuristic Algorithms for the Routing and Wavelength Assignment of Scheduled Lightpath Demands in Optical Networks.
IEEE Journal on Selected Areas in Communications 24 (8), 2-15, 2006.
%\bibitem{Zang}
%H. Zang, J.P. Jue, B. Mukherjee:
%A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks.
%SPIE Optical Networks Magazine 1 (1), 47--60, 2000.




\end{thebibliography}

\end{document}

