Constraint Solver Part 11: Graph Coloring Part 2

Series: Constraint Solver in Julia

This is part 11 of the series about: How to build a Constraint Programming solver?

In the last post we created the != constraint to solve graph coloring. The problem is that we currently can’t specify that we want to minimize the number of colors used. We therefore tried it out with four colors because based on the four color theorem this should work and well it did. After that we checked whether that is the best solution by removing the fourth color. It turned out to be infeasible.

I want to add the possibility to optimize in this post. We have to keep track of a bit more information for this which we will do first before implementing the optimization step.

First of all I want to show you another interesting way to solve graph coloring using Mixed Integer Programming (MIP). I did a series on how to solve linear problems (see Simplex Method) and also a post on how to use a MIP solver to solve small Travelling Salesman Problems TSP solver.

Where the later one is currently out dated as it uses an older version of JuMP.jl and Julia itself.

Comparison with MIP

Let’s compare our current constraint solver approach without optimization step with a MIP approach. We will use GLPK.jl which is a wrapper to call GLPK in Julia. It works using JuMP.jl which is the Julia package for mathematical programming.

I got the idea from this blog post on graph coloring written in R.

What are the rules? Or how can we write the graph coloring problem as a mixed integer (here actually all variables are integer) linear problem?

We could use the same variable structure:

  • A variable for each state having the possible values 1,2,3 & 4

but it’s not that easy to have a != in a linear problem.
Therefore we use a different approach namely we have four binary variables for each state. If we don’t know the four color theorem we need to add more colors same is true if we don’t actually have a valid 2D Map. Graph coloring can also be used if we have a graph of nodes and edges we want to separate the nodes in such a way that two connected nodes don’t have the same color.

Pseudocode:

c[s][1,2,3,4] = {0,1}

c[1][1] = 1 would mean that we use color 1 (red) for the state of Washington which was the first in our list of states.

The first constraint then is quite obvious

\[
\sum_{i=1}^4 c[s][i] = 1 \quad \forall s \in \text{States}\]

Meaning: Each state has exactly one color.

Now we also want to minimize the number of colors we use….