Graph Coloring - Weighted Vertex Coloring Problem

This project proposes several local searches and an MCTS algorithm for the weighted vertex coloring problem (WVCP).

This problem is an variant of the Graph Coloring Problem. Given a weighted graph G=(V,E), the set of vertices V, the set of edges E and let W be the set of weights w(v) associated to each vertex v in V, the WVCP consists in finding a partition of the vertices V in into k color groups S=(V_1,...,Vk) (1 \leq k \leq |V|) such that no adjacent vertices belong to the same color group and such that the objective function f(S) = \sum_{i=1}^{k}\max_{v\in V_i}{w(v)} is minimized.

This project is coded in C++ for the calculation part and in Python for the data analysis. This work is related to the article :

Grelier, C., Goudet, O., Hao, J.-K., 2022. On Monte Carlo Tree Search for Weighted Vertex Coloring. arXiv:2202.01665 [cs]. https://arxiv.org/abs/2202.01665

Requirements

To compile this project you need :

• cmake 3.14+
• Doxygen (optional, to build the documentation)
• Python (used with 3.8+ for the slurm job generators, data analysis and documentation)

Run the project

Clone the project

git clone https://github.com/Cyril-Grelier/gc_wvcp_mcts

Go to the project directory

cd gc_wvcp_mcts

Load the instances

git submodule init
git submodule update

Build and compile the project :

./scripts/build.sh

Run the project :

cd build
./gc_wvcp --help

Run with slurm

You can find a generator of “to_eval” file to run jobs with slurm or GNU parallel. Set the desired instances, random seed and different parameters in scripts/generator_to_eval_ls.py (for local search) or scripts/generator_to_eval_mcts.py (for mcts) and run the script with python (no particular packages are required) python scripts/generator_to_eval_mcts.py and it will generate output directory and a to_eval file which will contain each command line argument to run with slurm or GNU Parallel.

Create Python environment for data analysis or documentation

Make sure to create the environment for python and activate it before running scripts for data analysis or documentation :

./scripts/build_python.sh
source venv/bin/activate

Data analysis

scripts/generate_table.py takes raw data and convert it to xlsx files (in xlsx_files repertory) with colored best scores, p-value calculation.

Make sure to set all required methods, instances and output names directly in the script before running it.

Results

You can find the raw results in outputs from runs of the code on different instances on the cluster of Nantes : https://ccipl.univ-nantes.fr/ (nazare nodes). These files are in csv format with the header on the first line, followed by each improving solution found during the search (with the complete solution), the last line corresponds to the best solution found during the whole search with the number of iterations, the time,… at the end of the run. The processed data can be found in xlsx_files (files generated by scripts/generate_table.py script). In those files, the results are slightly different comparing to the results in the article as they have been computed on a different CPU but the tendency stay the same.

Documentation

You can generate the documentation by running :

cd docs
make html

The doc main page will be located in : docs/_build/html/index.html. It’s a basic documentation generated from comments in the code.

Acknowledgements

We would like to thank Dr. Wen Sun for sharing the binary code of their AFISA algorithm [1] (the AFISA algorithm have been reimplemented from the article, afisa_original), Dr. Yiyuan Wang for sharing the code of their RedLS algorithm [2] (the RedLS algorithm have been reimplemented from the article, redls) and Pr. Bruno Nogueira for sharing the code of their ILS-TS algorithm [3] (some part of the code have been used and adapted to the implementation of the project, ilsts).

• [1] Sun, W., Hao, J.-K., Lai, X., Wu, Q., 2018. Adaptive feasible and infeasible tabu search for weighted vertex coloring. Information Sciences 466, 203–219. https://doi.org/10.1016/j.ins.2018.07.037
• [2] Wang, Y., Cai, S., Pan, S., Li, X., Yin, M., 2020. Reduction and Local Search for Weighted Graph Coloring Problem. AAAI 34, 2433–2441. https://doi.org/10.1609/aaai.v34i03.5624
• [3] Nogueira, B., Tavares, E., Maciel, P., 2021. Iterated local search with tabu search for the weighted vertex coloring problem. Computers & Operations Research 125, 105087. https://doi.org/10.1016/j.cor.2020.105087