Hausdorff School on Computational Combinatorial Optimization

Exercise II: ILP Formulations for Graph Coloring

author: Stephan Held

date: 11.09.2022

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?