# Hausdorff School on Computational Combinatorial Optimization

## Exercise II: ILP Formulations for Graph Coloring

### disclaimer: This exercise is built around the paper Strengthened Partial-Ordering Based ILP Models for the Vertex Coloring Problem, https://arxiv.org/abs/2206.13678 by A.Jabrayilov & P.Mutzel, including their original source code. A preceding paper appeared at LATIN 2018.

First, will learn and use existing Python code to solve the graph coloring problem with the assignment formulation. Then, we will implement various improved formulations. For comparison, we will also use the branch & price implementation exactcolors by William Cook, Stephan Held, and Ed Sewell.

The underlying LP & ILP solver will be Gurobi.

## Copying the source code

First, we copy an existing implementation of the assignment formulation for graph coloring to a new directory and move to that directory.

``````  rsync -vau /home/sheld/public/COLORING/ COLORING/
cd COLORING/``````

The code consists of two files. The file `main.py` contains the main function that reads a graph from a DIMACS file and passes it to the color function implemented in `ass.py`. For convenience, it also contains the link `dimacs` to a folder with the DIMACS graph coloring instances.

Study and understand how the IP model is currently defined in `ass.py`. The two most important Gurobi functions are Model.addVar for adding new varibles and Model.addConstr for adding new constraints. Other Gurobi functions initialize the model, set some parms and the objective are set, and optimize the model. Observe, how the variable references returned by Gurobi are stored in a dictionary and how the colores within the large clique are fixed in advance by setting the lower and upper bounds of the corresponding variables to 1 (creating superfluous variables in Gurobo, though).

As a start, let us color a simple instance:

``   python3 main.py --dimacs_graph dimacs/anna.col``

The program first computes a heuristic solution using 11 colors and (heuristically) a clique of size 11. Thus, the coloring number is determined w/o building an ILP. Next example:

``   python3 main.py --dimacs_graph dimacs/myciel3.col``

The heuristic solution has 4 colors and the best found clique has 2 vertices. Actually, the dimacs/myciel*col instances are Mycielski graph with clique number 2 but increasing coloring numbers. What is happening then?

Next try

``````   python3 main.py --dimacs_graph dimacs/myciel4.col
python3 main.py --dimacs_graph dimacs/myciel5.col
python3 main.py --dimacs_graph dimacs/myciel6.col``````

What is the output? You could change the default time limit of 60 seconds via

``   python3 main.py --time_limit <seconds> ...``

But instead, we want to strengthen the formulation according to the lecture. Start with the basic partial-order based LP formulation. We recommend copying the file

`cp ass.py pop.py`

and adjusting only the creation of the IP model in `pop.py`.

To use the new model, replace in `main.py`

`import ass as colmip`

by

`import pop as colmip`

Now, rerun

``   python3 main.py --dimacs_graph dimacs/myciel5.col``

How does it affect the running time?

You can also compare to an efficient implementation of branch & price based on a set cover formulation for coloring, e.g.

``/opt/exactcolors/color  dimacs/myciel5.col  -l 60``

Here `-l 60` sets a time limit of 60 seconds to the branching phase.

Run all variants on other instances, e.g.

``````   python3 main.py --dimacs_graph dimacs/DSJC129.9.col

/opt/exactcolors/color  dimacs/DSJC129.9.col  -l 60``````

or

``````   python3 main.py --dimacs_graph dimacs/DSJC129.5.col

/opt/exactcolors/color  dimacs/DSJC129.5.col  -l 60``````

Question: Can we trust the result returned by the ILP formulations?