[![INFORMS Journal on Computing Logo](https://INFORMSJoC.github.io/logos/INFORMS_Journal_on_Computing_Header.jpg)](https://pubsonline.informs.org/journal/ijoc)

# A stable set formulation for the Equitable Coloring Problem

This archive is distributed in association with the [INFORMS Journal on
Computing](https://pubsonline.informs.org/journal/ijoc) under the [MIT License](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](https://doi.org/10.1287/ijoc.2025.1294) 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{Olariu2026,
  author =        {E. F. Olariu, C. Frăsinaru},
  publisher =     {INFORMS Journal on Computing},
  title =         {{A stable set formulation for the Equitable Coloring Problem}},
  year =          {2026},
  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

The files from this repo should be saved locally in a project with the following structure:

```
project/
│
├── bin/                      # Compiled .class files (CuttingPlane.class, BranchPrice.class)
└── lib/                      # The libraries required: gurobi.jar, graph4j-1.0.8.jar, etc.
├── src/                      # The .java source files
└── run.bat                   # Utility file for running the algorithms in Windows
└── run.sh                    # Utility file for running the algorithms in Linux
│
data/                         # not included
│
└── EqCol/
    ├── instances/            # Input .col files
    └── results/              # Output results

```

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](https://mat.tepper.cmu.edu/COLOR02/INSTANCES)


## Ongoing Development

This code is being developed on an on-going basis at the author's
[Github site](https://github.com/fe-olariu/EqColStableForm).

## Support

For support in using this software, submit an
[issue](https://github.com/fe-olariu/EqColStableForm/issues/new).
