In previous posts I have presented separately the graph coloring problem, as well as its generalization, the partitioned graph coloring problem, and linear programming. It is time to put both of them toghether, by modelling an instance of graph coloring using linear programming.
What we need to model
First we have to determine what we want to model. We will start with the standard graph coloring problem and introduce partitions later, so we will need a way to express the statement that we "assign color j to node i" using variables.
We will also have to find a way to express the constraints that every node must be colored, and no two adjacent nodes can share the same color, as well as specifying our objective to be to use as few different colors as possible.
Variables
Even though there are lots of different linear programming models for the coloring problem, we will present the most classic one, which is also the easiest to understand. We will use two different type of binary variables:
- \(x_{ij}\) variables that will be true if and only if node \(i\) is assigned color \(j\)
- \(w_j\) variables that will be true if at least one node is assigned color \(j\)
Note that what we have here are boolean or binary variables, as we want so specify boolean conditions. This means that all variables are restricted to have integral value and be between 0 and 1. This is why this problem is called a binary linear programming problem, which are a particular case of integer linear programming. We will later see what happens if we do not impose these restrictions on our variables.
Objective
Our objective will be to use as few different colors as possible, which we can express as minimizing the number of \(w_j\) variables that are true:
$$\min \sum _j w_j $$
Easy enough, and this explains why we had to introduce the artificial \(w_j\) variables. We will see how we relate them with the \(x\) variables with appropriate restrictions.
Constraints
First of all we must specify that every node is assigned exactly one color. Since we have boolean variables for each node-color combination, we simply have to request that the sum over all colors for a single node is equal to one:
$$ \forall i \in V \quad \sum _j x_{ij} = 1 $$
Color conflict constraints will be specified over every pair of adjacent nodes, for every possible color they can be assigned. What we want to express is that given a color and a pair of adjacent nodes, at most one of them may have that color assigned:
$$ \forall u,v \in E, j \in C \quad x_{uj} + x_{vj} \leq 1 $$
This restrictions ensures that at most one of the two variables will be true, effectively avoiding color conflicts.
As for \(w_j\) variables, one way to handle them is to simply make sure that if any node is colored with color \(j\) then \(w_j\) is set to true, by setting \(w_j\) as an upper bound for every \(x_{ij}\):
$$ \forall i \in V, j \in C \quad x_{ij} \leq w_j $$
However, if the graph has no isolated nodes, we can take advantage of color conflict constraints and reuse them to force \(w_j\) variables to be true if one of the two adjacent nodes uses color \(j\):
$$ \forall u,v \in E, j \in C \quad x_{uj} + x_{vj} \leq w_j $$
Using these sets of constraints we have successfully modelled a graph coloring problem.
Generalizing for Partitioned Coloring
Partitioned coloring follows the same rules as standard graph coloring, with the same objective, but with the slight difference that not every node must be colored, but a single node within every partition.
The same variables and objective function are used as in the model presented so far, and color conflict constraints are also the same. The only change will be in the first constraint, which requires that every node is colored:
$$ \forall P_k \in P \quad \sum _{i in P_k} \sum _j x_{ij} = 1 $$
Now we require that the sum over all node-color combinations in each partition is equals to one, which ensures that a single node is assigned a single color in every partition. This constitutes the most basic formulation for partition coloring.
An example...
Let's go back to our old diamond partitioned graph:
We know that we will be needing at most two colors for coloring this graph, as it has two partitions, and the worst case would be having to assign a different color to each partition, so our variables will be all \(x_{ij}\) and \(w_j\) with \(i\) ranging from 1 to 4 and \(j\) from 1 to 2.
First of all, our objective function, which minimizes the sum over all colors:
$$\min w_1 + w_2 $$
Coloring each partition comes next, we require that both partitions have exactly one node colored:
$$ x_{11} + x_{12} + x_{21} + x_{22} = 1 $$
$$ x_{31} + x_{32} + x_{41} + x_{42} = 1 $$
Finally, color conflict constraints are applied to every edge-color combination possible in the graph. Note that adjacent nodes within the same partition can be disregarded, as we have forced that at most one of them can be colored with the previous set of constraints.
These two constraints handle nodes \(v_1\) and \(v_4\) for all possible colors:
$$ x_{11} + x_{41} \leq w_1 $$
$$ x_{12} + x_{42} \leq w_2 $$
Now for the other two pairs of adjacent nodes:
$$ x_{11} + x_{31} \leq w_1 $$
$$ x_{12} + x_{32} \leq w_2 $$
$$ x_{21} + x_{31} \leq w_1 $$
$$ x_{22} + x_{32} \leq w_2 $$
With these restrictions we have a complete formulation for the partitioned coloring of this graph. In a future post we will see the optimal values for these system of linear restrictions with and without integrality restrictions, and see why they are so necessary for boolean formulations.