Search for projects
Variable Neighborhood Search for the Partition Graph Coloring Problem
Lorenz Leutgeb, Moritz Wanzenböck
Today's "always-on" mentality and increased use of the internet introduces new challenges when designing communication networks. Modern fiber-optic networks can be modelled as mathematical structures to overcome those defiances. This project emphasizes on the distribution of wavelengths (channels) in fiber-optic networks. By solving the Partition Graph Coloring Problem (PCP), the structure of target networks can be optimized in order to eventually save money. The PCP is of non-deterministic polynomial-time complexity, meaning it belongs to the group of problems most difficult to solve. Therefore clever methods must be developed to obtain a solution in reasonable time. An adoption of Variable Neighborhood Search (VNS) for the PCP is proposed and implemented.