The band collocation problem: A library of problems and a metaheuristic approach

Far Eastern Federal University, Vladivostok;Higher School of Economics, Nizhny Novgorod;Novosibirsk State University;Russian Foundation for Basic Research9th International Conference on Discrete Optimization and Operations Research, DOOR 2016 -- 19 September 2016 through 23 September 2016 --In this paper, we consider the Band Collocation Problem (BCP) which may find an application in telecommunication networks, to design an optimal packing of information flows on different 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 different 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. Copyright © by the paper's authors