A VNS approach to solve the Partition Graph Coloring Problem.
We use onestepCD from [1] to find an initial solution and then iteratively apply various neighborhood improvement strategies.
This implementation uses various components of the boost C++ libraries.
To compile with support for Ubigraph, further libraries are needed.
| Package | Component |
|---|---|
libboost-dev |
core |
libboost-program-options-dev |
core |
libxmlrpc-c3-dev |
ubigraph |
freeglut3 |
ubigraph |
wmctrl |
scripts |
| Package | Component |
|---|---|
boost-devel |
core |
freeglut |
ubigraph |
xmlrpc-c-devel |
ubigraph |
wmctrl |
scripts |
[1] Guangzhi Li, Rahul Simha, The partition coloring problem and its application to wavelength routing and assignment, In Proceedings of the First Workshop on Optical Networks, 2000
[2] Thiago F. Noronha, Celso C. Ribeiro, Routing and wavelength assignment by partition colouring, In European Journal of Operational Research, Volume 171, Issue 3, 2006, Pages 797-810, ISSN 0377-2217
[3] Thiago F. Noronha, Mauricio G.C. Resende, Celso C. Ribeiro, Instances for the routing and wavelength assignment problem