A stable set formulation for the Equitable Coloring Problem

This archive is distributed in association with the INFORMS Journal on Computing under the MIT License.

The software and data in this repository are a snapshot of the software and data that were used in the research reported on in the paper A stable set formulation for the Equitable Coloring Problem by Emanuel Florentin Olariu and Cristian Frăsinaru.

Important: This code is being developed on an on-going basis at https://github.com/fe-olariu/EqColStableForm. Please go there if you would like to get a more recent version or would like support

Cite

To cite the contents of this repository, please cite both the paper and this repo, using their respective DOIs.

https://doi.org/10.1287/ijoc.2025.1294

https://doi.org/10.1287/ijoc.2025.1294.cd

Below is the BibTex for citing this snapshot of the repository.

@misc{CacheTest,
  author =        {E. F. Olariu, C. Frăsinaru},
  publisher =     {INFORMS Journal on Computing},
  title =         {{A stable set formulation for the Equitable Coloring Problem}},
  year =          {2020},
  doi =           {10.1287/ijoc.2025.1294.cd},
  url =           {https://github.com/INFORMSJoC/2025.1294},
  note =          {Available for download at https://github.com/INFORMSJoC/2025.1294},
}  

Description

A new integer programming model is introduced based on a stable set formulation for the decision version of the Equitable Coloring Problem. This new formulation is integrated into two Binary Search-like algorithms, the efficiency of which we have tested onto some instances from literature. The numerical results show that this new approach was able to improve the known lower bounds of equitable chromatic number for two thirds of the tested instances and found the equitable coloring number for two instances.

This repository contains two Java implementations of optimization algorithms for solving the Equitable Coloring Problem: CuttingPlane and BranchPrice

Replicating

Running the algorithms can be done using run.bat or run.sh files.

The first argument is the name of the algorithm, the second argument is the name of the input file.

Examples:

run.bat BranchPrice le450_25c.col     # Windows
.\run.sh CuttingPlane dsjc250.5.col   # Linux

If running on Linux, make sure run.sh is executable:

chmod +x run.sh

Benchmark instances can be obtained at: https://mat.tepper.cmu.edu/COLOR02/INSTANCES

Requirements

• Java 11 or newer
• Gurobi Optimizer 13
  • Must be installed and licensed.
  • Gurobi Java bindings must be correctly set in your environment.

Windows:

GUROBI_HOME="C:\Apps\gurobi1300\win64"    # Modify path accordingly
PATH="%PATH%;%GUROBI_HOME%\bin"
LD_LIBRARY_PATH="%LD_LIBRARY_PATH%;%GUROBI_HOME%\lib"

Linux:

GUROBI_HOME="/opt/gurobi1300/linux64"     # Modify path accordingly
PATH="$PATH:$GUROBI_HOME/bin"
LD_LIBRARY_PATH="$LD_LIBRARY_PATH:$GUROBI_HOME/lib"

Ongoing Development

This code is being developed on an on-going basis at the author's Github site.

Support

For support in using this software, submit an issue.