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.
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?