Santiago Palladino

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.

Before going into how to solve the partitioned graph coloring problem using integer linear programming (which is the goal of my thesis), I thought it would be a good idea to actually explain what is the partitioned graph coloring problem (or PCP from now on).

Graphs and partitions

First of all, graphs. Formally, a graph is defined as two sets: a set of nodes which compose the graph, and a set of edges between pairs of nodes. For example, the definition for the so-called diamond graph is the following:

$G = V,E = \{1,2,3,4\}, \{ (1,2),(2,3),(3,4),(4,1),(1,3) \}$

And a representation for it could be the following:

While this is the simplest form of a graph, several additions can be made: weights or attributes can be assigned to either nodes or edges; edges can be directed; multiple edges can be allowed between pairs of nodes; etc. The modification we will be dealing with in this scenario is partitioning the graph's nodes. As such, the graph is now defined as three sets: besides the nodes and edges, the set of partitions, where each partition is a non-empty set of nodes such that every node belongs to exactly one partition.

A possible partitioning of the diamond graph previously presented could be the following:
$G = V,E,P = \{1,2,3,4\}, \{ (1,2),(2,3),(3,4),(4,1),(1,3) \}, \{ \{1,2\}, \{3,4\} \}$

Coloring

Having defined the kind of graphs we will be working with, it's time to define the problem itself. The graph coloring problem consists in defining a function that assigns a label (a "color") to each node in the graph, with the restriction that every pair of adjacent nodes must have different colors.

For example, a valid coloring for the diamond graph presented earlier would be the following:

The goal here is to find a valid coloring that uses the minimum possible number of different colors. This value is called the chromatic number of a graph.

Determining if there is a valid k-coloring (coloring that uses exactly k colors) for a particular graph is usually difficult to determine, where difficult implies that it requires a huge computational effort; for those of you with background on CS, this problem is known to be NP-complete.

For .NET fans, it is worth checking the posts that Eric Lippert has been uploading recently on making a backtracking algorithm for the coloring problem using C#.

Partitioned Coloring

The coloring problem has several variants. For example, it might be of interest to minimize the not only the number of different colors used, but also the difference between how many nodes are painted with each color. Or allow that adjacent nodes have the same color, incurring in a penalty in an objective function, if it allows the usage of fewer colors.

In this case, the partitioned graph coloring consists in coloring one node per partition, with the restriction that two adjacent nodes may not have the same color. The difference with the standard coloring is that not all nodes must be colored, only one in each partition.

Going back to our diamond example, by cleverly picking which nodes to color in each partition, we can partition-color the whole graph using a single color:

Even though not all nodes are to be colored, this variant of the problem is still computationally difficult (NP-complete) to solve. Most approaches to it are heuristic, this is, they do not find the optimal solution, but offer a reasonable one in a reasonable time, as all algorithms that guarantee finding the best solution take too long to execute for large graphs.

Our goal will be to use a technique called integer linear programming to solve this problem, obtaining the exact solution in a reasonable time, for medium-sized instances.