# A Comparative Evaluation of Nature Inspired Algorithms for Telecommunication Network Design
## 2 Problem Formulation  
In this section, the UW-WDM network optimization problem is formulated using MIP [10]. For this purpose the following sets are defined:  
* set of all nodes;
* set of transponders;
* set of frequency slices;
* set of edges;
* set of paths between nodes \(n,n^{\prime}\in\mathcal{N}\) for transponder \(t\in\mathcal{T}\); \(p\subseteq\mathcal{E}\);
* set of bands;
* set of frequency slices used by band \(b\in\mathcal{B}\); \(\mathcal{S}_{b}\subseteq\mathcal{S}\); \(\bigcup\limits_{b\in\mathcal{B}}\mathcal{S}_{b}=\mathcal{S}\);
* set of frequency slices that can be used as starting; slices for transponder \(t\in\mathcal{T}\); \(\mathcal{S}_{t}\subseteq\mathcal{S}\).  
Notice that the power budget constraints are taken into account in the model by limiting sets \(\mathcal{P}_{(n,n^{\prime},t)}\). In this approach, the sets are precomputed and contain only paths that are feasible from the point of view of the power budget.  
We use the following variables:  
* binary variable, equal to 1 if band \(b\) is used on edge \(e\) and 0 otherwise;
* binary variable that equals 1 if transponders \(t\) are installed between node \(n\) and node \(n^{\prime}\), routed on path \(p\) and start on frequency slice \(s\in\mathcal{S}_{t}\), and 0 otherwise.
* In the model, the following constants are used:  
* cost of using band \(b\) at a single edge;
* cost of using a pair of transponders \(t\) in band \(b\);
* bitrate provided by transponder \(t\);
* bitrate demanded from node \(n\) to node \(n^{\prime}\);
* binary constant that equals 1 if transponder \(t\) using bandwidth starting at frequency slice \(s\) also uses frequency slice \(s^{\prime}\); 0 otherwise.  
In the cost model EDFAs, preamplifiers, boosters, ILAs and transponders are included in \(\zeta(b)\) and \(\zeta(t,b)\) but not WSSs and filters since the latter devices cannot be subject to optimization.  
The optimization model is as follows:  
\[\min\sum_{b\in\mathcal{B}}\big{(}\xi(b)\sum_{e\in\mathcal{E}}y_{be}+ \sum_{t\in\mathcal{T}}\xi(t,b)\sum_{n,n^{\prime}\in\mathcal{N}}\sum_{p\in \mathcal{P}_{(n,n^{\prime},t)}}\sum_{s\in\mathcal{S}_{t}}x_{tnn^{\prime}ps}\big{)} \tag{1}\] \[\sum_{t\in\mathcal{T}}\sum_{p\in\mathcal{P}_{(n,n^{\prime},t)}} \sum_{s\in\mathcal{S}_{t}}v(t)x_{tnn^{\prime}ps}\geq d(n,n^{\prime})\quad \forall n,n^{\prime}\in\mathcal{N}\] (2) \[\sum_{t\in\mathcal{T}}\sum_{n,n^{\prime}\in\mathcal{N}}\sum_{p\in \mathcal{P}_{(n,n^{\prime},t)}}\sum_{s\in\mathcal{S}_{t}}u(t,s,s^{\prime}) \cdot x_{tnn^{\prime}ps}\leq y_{be}\quad\forall e\in\mathcal{E},\ \forall b\in \mathcal{B},\ \forall s^{\prime}\in\mathcal{S}_{b} \tag{3}\]  
The subject of minimization is the cost of installed amplifiers and transponders in (1). Constraints (2) ensure that all demands are satisfied. Constraints (3) ensure that each frequency slice at each edge is not used more than once. Moreover, they ensure that using a band at an edge results in installing appropriate amplifiers.  
In this contribution the CAPEX minimization problem is considered and several techniques are applied in order to reduce the calculation time. The motivation for reducing the calculation time of the CAPEX minimization problem is two fold. First of all the CAPEX minimization should be performed each time new capacity is needed following a request coming from a customer. Hence, smaller calculation time is of clear benefit. Secondly, it was observed that the calculation time of standard optimization methods (e.g., ILP) growths rapidly with the number of network nodes [7]. Thus, for large networks, application of heuristic methods becomes indispensable.