Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
A VNS approach to solve the Partition Graph Coloring Problem.
C++ Python Makefile Shell

Fetching latest commit…

Cannot retrieve the latest commit at this time

Failed to load latest commit information.
include
instances @ 9c0e4fb
units
.gitignore
.gitmodules
.travis.yml
LICENSE
Makefile
README.md
Solution.cpp
StoredSolution.cpp
behemoth.sh
crunch.py
demo.sh
full.sh
generator.py
main.cpp
oneStepCd.cpp
outputter.py
pcp2gv.py
setup-ubigraph.sh
vns.cpp

README.md

pcp-vns

Build Status

A VNS approach to solve the Partition Graph Coloring Problem.

Approach

We use onestepCD from [1] to find an initial solution and then iteratively apply various neighborhood improvement strategies.

Dependencies

This implementation uses various components of the boost C++ libraries.

To compile with support for Ubigraph, further libraries are needed.

Ubuntu

Package Component
libboost-dev core
libboost-program-options-dev core
libxmlrpc-c3-dev ubigraph
freeglut3 ubigraph
wmctrl scripts

Fedora

Package Component
boost-devel core
freeglut ubigraph
xmlrpc-c-devel ubigraph
wmctrl scripts

References

[1] G. Li, R. Simha, "The partition coloring problem and its application to wavelength routing and assignment", in: Proceedings of the First Workshop on Optical Networks, 2000. (see http://www.seas.gwu.edu/~simha/research/partcolor.ps)

[2] T.F. Noronha, C.C. Ribeiro, "Routing and wavelength assignment by partition coloring", in: European Journal of Operational Research 171:797-810, 2006

[3] T.F. Noronha, M.G.C. Resende, C.C. Ribeiro, "Instances for the routing and wavelength assignment problem". (see http://www.ic.uff.br/~celso/grupo/rwa.html)

Something went wrong with that request. Please try again.