Integer Linear Programming Implementation for Packing and Coloring in Graphs

This code uses the formulation from Shao & Vesel’s 2015 work, Modeling the packing coloring problem of graphs¹.

Setup Instructions

Follow these steps to set up the project on your local machine:

Prerequisites

Ensure you have the following installed:

• Python 3.10 or higher
• pip (Python package manager)

Installation

1. Create a virtual environment (optional but recommended):

   python3 -m venv venv
   source venv/bin/activate  # On macOS/Linux
   venv\Scripts\activate     # On Windows

2. Install dependencies:

   pip install -r requirements.txt

Notes

• Ensure CPLEX is installed and configured. Setting up the CPLEX Python API

Usage

1. Run the main script:

   python main.py

2. View generated graphs:

   • Graph files will be saved in the graphs directory.

3. Modify parameters:

   • Update P_n, B_n, or K_n values in main.py to customize the graph generation.

References

Footnotes

1. Z. Shao and A. Vesel, “Modeling the packing coloring problem of graphs,” Applied Mathematical Modelling, vol. 39, no. 13, pp. 3588–3595, 2015. DOI: 10.1016/j.apm.2014.11.060. ↩