In this paper, we consider the Band Collocation Problem (BCP) which may nd an application in telecommunication networks, to design an optimal packing of information ows on di erent wavelengths into groups for obtaining the highest available cost reduction using wavelength division multiplexing (WDM) technology. We give a review of its mathematical models. The linear and nonlinear models have been implemented in GAMS (the General Algebraic Modeling System) and solved using the CPLEX and KNITRO solvers, respectively. Then, we introduce the BCP Library (BCPLib) including 1296 problem instances with di erent properties that can be accessed at http://www.izmir.edu.tr/bps. Finally, we improve a simulated annealing (SA) meta-heuristic to solve the BCP. The proposed algorithm is performed using two local search methods for several test instances of the BCPLib and compared with the solutions obtained by a genetic algorithm. Experimental results showed that the proposed algorithm improves the quality of solutions.
The Bandpass Problem (BP) whose rst mathematical model was presented in 2009 is a combinatorial optimization problem which may be used in telecommunication systems [1]. Due to the development in the technology, some problems become invalid or useless and they need to be updated. In this sense, Nuriyev et. al. announced the Band Collocation Problem (BCP) by extending the BP due to incompatibility with real life implementations at the present time [7].
The BP is related to transmitting data over ber optic networks using the Dense Wavelength Division Multiplexing (DWDM) technology [1]. The data is transmitted from a source to other stations on di erent wavelengths in a single ber optic cable. Copyright c by the paper's authors. Copying permitted for private and academic purposes. In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org Stations add/drop data onto/from the cable via an optical device called Add/Drop Multiplexers (ADM). Special cards in ADMs control each wavelength. They can add/drop (extract) data at some wavelengths to/from a network path [5]. Stations do not have to receive all data on the cable.
Each special card is normally responsible for one wavelength. However, according to the BP, a practical programmable ADM can add/drop multiple wavelengths if they are neighboring to each other, that is, if they are consecutive. In the BP, a group of consecutive wavelengths is called bandpass and the length of a bandpass is represented by a positive integer B called bandpass number.
Companies want to reduce the costs of constructing the network. Actually, this is the goal of the BP by maximizing the number of bandpasses. The key idea of the BP is to gather up requested data's wavelengths at any station.
In order to model this problem, we use a binary matrix corresponding to the network tra c. Consider a communication network. The communication is conducted on m di erent wavelengths to carry data to be sent to n di erent stations. This situation is described by a binary matrix A = aij: if data carried on wavelength i = 1; :::; m is requested by station j = 1; :::; n then aij = 1 otherwise aij = 0.
Consider as an example matrix A shown in Fig. 1 which represents a network tra c. For this example, if each special card in ADMs controls one wavelength, then we need 21 cards. If some special cards are programmed to handle two consecutive wavelengths (this means that the bandpass number B is 2), then we would need 13 cards (8 for bandpasses, see Fig. 1.(a), 5 for single). If some special cards are programmed for three consecutive wavelengths (this means B is 3), then would we need 21 cards since there is no any bandpass when B = 3 as it can be seen in Fig. 1.(b).
Special cards in ADMs are expensive and IT managers try to reduce the number of these cards used in ADM. How is it possible? The answer is to reorder the wavelengths. For this purpose, the BP asks reordering of the rows of a given matrix so that the number of B non-overlapping consecutive 1's is maximized. Note that in the communication network, reordering of the rows of the matrix simply corresponds to a reassignment of the DWDM wavelengths.
Fig. 2 shows a reordering of the rows of the matrix given in Fig. 1. For this reordering, if some special cards are programmed for B = 2 consecutive wavelengths, then we need 13 cards again (8 for bandpasses, 5 for single). However, if some special cards are programmed for B = 3 consecutive wavelengths, then we need 13 cards (4 for bandpasses, 9 for single). Thus, this reordering of rows allows the use of fewer cards when B = 3.
It is clear that to nd an optimal solution to the BP, we must perform an exhaustive search over all row permutations. There are total of m! di erent permutations of m wavelengths. This number grows faster than exponentially with m. Therefore, this is not reasonable. Babayev et al. also have proved that the BP is NP-hard [1].
Recent changes in ADM technology made the BP ine ective. We can explain the de ciencies of the BP as follows:
Technology allows an ADM to drop a wavelength even if it does not carry any information. Therefore, (a) a bandpass may contain zero elements. (b) The bandpass number B may be not xed. (c) the BP ignores costs of the programmable cards. Thus, the BCP is proposed.
In the next section, we give a review of the mathematical models of the BCP. In Section 3, we introduce a library of problem instances for researchers to develop e cient computational solution methods, open for public use. In Section 4, we improve a simulated annealing (SA) metaheuristic to solve the BCP and also present computational results. 2
In this section, we review all models of the BCP. We rst introduce some
notation that will be used throughout the models. Let A = (aij ) be a binary matrix
of dimension m n, Bk = 2k be a length of bands and ck be a cost of the
BkBand, where (k = 0; 1; : : : ; t = blog2mc). is a permutation of the rows such that
= ( (
The combinatorial formulation of the BCP introduced rst by Nuriyev et al. is the following [7].
t m Bk+1 n Minimize X X X ckyk(i)j
k=0 i=1 j=1 subject to
Bk yk(l)j m X zk(i)j ; k = 0; :::; t; j = 1; :::; n; l = 1; :::; m Bk + 1; yk(l)j + l+Bk 1 t
X X yp(i)j i=l+1 p=0 1; k = 0; :::; t; j = 1; :::; n; l = 1; :::; m
Bk + 1; i=l t m Bk+1 X X k=0 i=1
Bk yk(i)j m X aij ; j = 1; :::; n; i=1 t X yk(i)j 1; i = 1; :::; m; j = 1; :::; n; k=0 t X zk(i)j aij ; i = 1; :::; m; j = 1; :::; n; k=0
t X zk(i)j 1; i = 1; :::; m; j = 1; :::; n; k=0 yikj ; zikj 2 f0; 1g; i = 1; :::; m; j = 1; :::; n; k = 0; :::; t;
The explanations of each constraint will be given at the end of this section. 2.2
A linear programming model of the BCP introduced rst by Gursoy et al. is the following [4].
subject to
t m Bk+1 n Minimize X X X ckyikj
k=0 i=1 j=1
m
X xir = 1; i = 1; : : : ; m
r=1
(
m X xir = 1; r = 1; : : : ; m i=1 k Bk ylj l+Bk 1 m
X X aij xir; k = 0; : : : ; t; j = 1; : : : ; n; l = 1; : : : ; m Bk + 1 (12) r=l i=1 t m Bk+1
X X k=0 m Bk+1
X
i=1
Bk yikj = l+Bk 1 i=1
X k
yij i=l
k Bk yij i=1 m X aij ; j = 1; : : : n i=1 m
X zikj ; k = 0; : : : ; t; j = 1; : : : ; n 1; k = 0; : : : ; t; j = 1; : : : ; n; l = 1; : : : ; m
Bk + 1 t X yij
k t k=0 m X zij
k k=0
1; i = 1; : : : ; m; j = 1; : : : ; n
X arj xri; i = 1; : : : ; m; j = 1; : : : ; n t r=1 X zikj 1; i = 1; : : : ; m; j = 1; : : : ; n k=0 xir; yikj ; zikj 2 f0; 1g; i; r = 1; : : : ; m; j = 1; : : : ; n; k = 0; : : : ; t: 2.3
A nonlinear programming model of the BCP introduced rst by Nuriyev et al. is the
following [8].
(
j=1 k Bk ylj subject to l+Bk 1 m
X X zikj xir; k = 0; : : : ; t; j = 1; : : : ; n; l = 1; : : : ; m
Bk + 1 (21)
r=l i=1
and (
The constraints (
The linear and nonlinear models have been implemented in GAMS (the General Algebraic Modeling System) and solved using the CPLEX and KNITRO solvers, respectively.
As an extension of the Bandpass problem, the BCP is NP-hard. Therefore, it is needed to improve heuristic or metaheuristic algorithms. Potential researchers working on the BCP may need problem instances to check and compare their solutions.
First of all, we focused on what the comparison criteria of the solution algorithms would be. Main question was what the changing of the results was depending on? So, we considered all components of the BCP such as number of rows, number of columns, cost of a Bk Band, density of the binary matrix.
Solution algorithms can be compared according to di erent number of rows, columns and di erent density of the binary matrix. Here, the density of a matrix is the ratio of the number of its nonzero entries to the total number of its entries.
It is clear that the upper bound of the length of a Bk Band depends on the number
of rows. For example, if the number of rows equals 12, then there are B0 = 20 = 1,
B1 = 21 = 2, B2 = 22 = 4 and B3 = 23 = 8 bands. The costs c1, c2, c3 and c4 are
corresponding to each of these bands. Now, we face with a new question: How should we
determine the costs? In particular, how should the price be increased from ci to ci+1?
It cannot be random, since it is not suitable to compare algorithms. So, we identi ed
six growth rates ( = 0.05, 0.1, 0.2, 0.3, 0.4 and 0.5) for this purpose, and used the
following formula for all problem instances:
ck+1 = (
In the library, there are three di erent matrices of the same type. (TX-M1, TX-M2 and TX-M3), there are six di erent cost alternatives for the same matrix.
There are currently available 72 matrix types, 216 di erent matrices and 1296 problem instances. Potential contributors to this library can provide their instances. Information on new instances or optimum solutions for library problems is also appreciated (to be included into the library). At this point we should note that a solution must contain the permutation (ordering) of rows of the matrix, the starting position of each a Bk Band in all columns and the total cost.
The Band Collocation Problem Library (BCPLib) is available online at http://www.izmir.edu.tr/bps. There are details about instances on \Remarks for Instances and Solutions" page. Fig. 3 shows the page of the Instances of Unknown Optimal Value which includes both the properties of 1296 instances and their excel le.
There will be properties of instances of known optimal value in \Instance of Known Optimal Value" and will be an excel le which will be included them. When we nd some solutions to the instances, we will share results in \Solution for Instances of Unknown Optimal Value" and \Solutions for Instances of Known Optimal Value" pages.
Fig. 4 shows an excel le which includes instances. Each work sheet in the le has a TXMY matrix and six cost ratios. 4
Simulated annealing (SA) is a popular metaheuristic approach for solving combinatorial optimization problems. The key point of simulated annealing is that it provides to nd a global optimum by escaping from local optima. SA introduced by Kirkpatrick et al. was inspired by the annealing process of physical systems [6]. At each iteration of a simulated annealing algorithm applied to an optimization problem, the objective function generates values for two solutions (the current solution and a newly produced solution) are compared. Better solutions are always accepted, while a fraction of bad solutions are accepted in the hope of escaping local optima in search of global optima. The probability of accepting bad solutions depends on a temperature parameter, which is typically geometrically decreasing with each iteration of the algorithm.
The pseudocode of the proposed SA algorithm is given in Algorithm 1. The proposed SA utilizes two reproduction operators, separately: one is to reverse a subset of the rows, the other is to swap two random rows. The rst reproduction operator is actually 2 opt local search method rst proposed by Croes [2] for solving the traveling salesman problem. The second one is a well-known interchange mechanism introduced by Osman and Christo des [10]. In each reproduction operator, the initial temperature was set to 5000. The cooling parameter = 0:9998. The SA terminates when the temperature falls down 0.1 as indicated line 4 of Algorithm 1. The other possible termination condition is independent of the temperature and says that the simulated annealing can stop when there is no change in the cost of the matrix after a xed number of iterations. Another termination condition is that the current cost value equals the optimum value. However, the optimum values of the test instances in BCPLib are not known, yet. Therefore, the SA algorithm lasts until the temperature falls down 0.1 which requires more time. The cost of the current solution (in line 5 of Algorithm 1) is computed by a dynamic programming algorithm proposed by Nuriyeva in [9].
Algorithm 1: Pseudocode of the SA. Our algorithm have been implemented in C and tested on i7-5600U machine with a 2.60 GHz processor and 8GB RAM. The test problems are taken from the BCPLib described above [11]. We perform 50 independent runs to get reliable statistical results. The entries of Table 1 and 2 presented below are:
Initial Cost : the cost value of the input matrix, m : the number of rows in the matrix, d : the density of 1's in the matrix, n : the number of columns in the matrix, ratio : the cost ratio , Best Genetic : the best value obtained by the genetic algorithm among
12 crossover and mutation techniques, Best : the best value obtained by the SA, Worst : the worst value obtained by the SA, Average : the average value among 50 runs, Improvement : the relative improvement between the best genetic value and our best value: (Be(sBt eGstenGeetnicetiBc)est) 100, Time : average CPU time in seconds.
The computational results presented in Table 1 and 2 show that our proposed SA using both local search methods gives better results than the results obtained by the genetic algorithm reported in [11]. The genetic algorithm and our proposed SA found the same best values for T1-M1-R10, T1-M1-R30, T3-M1-R10. This is probably that these values are the optimum values for the instances. As it can be seen interchange local search method compared to 2 opt is better in terms of the solution quality.
In this paper, we considered the Band Collocation Problem. We gave a review of its mathematical models. The linear and nonlinear models have been implemented in GAMS (the General Algebraic Modeling System) and solved using the CPLEX and KNITRO solvers, respectively. We also introduced the Band Collocation Problem Library (BCPLib) which is meant to provide researchers with a set of test problems having various properties. Generating problem instances whose optimal results known is the subject of future work. Finally, we improved a simulated annealing (SA) metaheuristic to solve the BCP. The proposed algorithm was performed using two local search methods for several test instances of the BCPLib and compared with the solutions obtained by a genetic algorithm. Experimental results showed that the proposed algorithm improves the quality of solutions. Moreover, interchange local search method is better than 2 opt local search method for the BCP in the SA algorithm.
The authors would like to thank the anonymous referees for their valuable comments that considerably improved the presentation of the paper. This work is supported by the Scienti c and Technological Re-search Council of Turkey-TUBITAK 3001 Project (Project No.:114F073) opt local search method. interchange local search method.