Santiago Palladino

After a long time, I have finally finished my thesis to get the MSc in Computer Science degree, from FCEN UBA. It has been almost a year since I started working in the thesis in the context of Manas Research, and before that I had been working on it for over another year within the computer science department.

The text of the thesis, called A branch and cut algorithm for the Partitioned Coloring Problem, can be downloaded in English here. The slides (in Spanish) that I'll be using tomorrow to present the thesis are also available here.

A sincere thank you to everyone who helped me during all this time with this work, and to Manas for sponsoring it!

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.

Despite being able to simply provide a link to wikipedia's already excellent article on Linear Programming, I wanted to provide a short introduction in order to present what I am doing exactly on my thesis in a future article.

Linear Programming is best described as a technique, in which we want to maximize or minimize an objective function subject to a set of constraints. It is called linear because both the objective function and the constraints are linear inequalities on the variables.

And just to make sure that no one is left behind: a linear function on a set of variables $x_1, x_2, \ldots, x_n$ is a function $a_0 + a_1 x_1 + a_2 x_2 + \ldots + a_n x_n$, where $a_0, a_1, a_2, \ldots, a_n$ are numbers. For example, $4 + 3x_1 - 2x_2$ is a linear function, whereas $x_1 * x_2 / x_3$ isn't.

Example: diet problem

A classical example for linear programming is the diet problem. We want to determine a diet that satisfies all of our nutritional requirements while keeping it as cheap as possible. We have a set of different foods that fulfill certain requirements by containing a certain amount of proteins, vitamins, etc; and each food has a certain price per kilogram. Needless to say, the values in the following table are completely fictional.

Suppose also that we need at least 60 units of each nutrient in our diet. Our objective will be to find a solution that specifies how much food of each type we should buy to cover all of our needs while keeping budget to a minimum.

In order to create a linear programming model, we must first define which variables we will be working with. We will define $x_i$ as how many kg of food $i$ we will be purchasing; therefore, our variables will be $x_A, x_B, x_C, x_P$.

Now we must specify our restrictions. We want to consume at least 60 units of each nutrient, and each food provides a certain amount per kg of it. For instance, we may express that we need 60 units of carbs as:

$$2 x_A + 4 x_B + 3 x_C + 8 x_P \geq 60$$

Note that each unit of apples provides 2 units of carbs, therefore the total amount of carbs provided by apples will be the product $2 \times x_A$; same holds for all foods.

Similar expressions can be derived for vitamins:

$$4 x_A + 5 x_B + 3 x_C + 2 x_P \geq 60$$

And for proteins:

$$2 x_A + 10 x_B + 4 x_C + 1 x_P \geq 60$$

Needless to say, all amounts must be positive, as we are buying food, not selling it. Therefore, we add constraints:

$$x_A, x_B, x_C, x_P \geq 0$$

The set of constraints we have built specify a set of valid or feasible solutions for us. For example, we will not accept a solution in which we purchase only 20kg of apples, since although that satisfies our vitamin intake, it does not satisfy carbs and proteins.

What we have to do now is, from every feasible solution, choose one that minimizes how much money we spend. So far, nothing prevents buying a whole supermarket of food from being a valid solution, albeit a very expensive one. In order to prevent that situation, we add an objective function to minimize, which is the cost of all the food we want to buy:

$$c(x) = 5 x_A + 20 x_B + 6 x_C + 2 x_P$$

The purpose of the objective function is to measure how good or bad a particular solution is, whereas the constraints restrict what we consider a valid solution for us. Putting all of them together, we have constructed a linear programming model for our diet problem.

Generalizing

A linear programming problem consists in the minimization of a linear objective function $c(x)$ subject to a set of linear constraints, which can be expressed as $Ax \geq b$, where $A$ is a matrix in which element $a_{ij}$ represents how much each unit of variable $j$ contributes to satisfying demand $b_i$ for product $i$.

Note that by using simple algebraic operations we can include all kind of non-strict linear constraints: $a(x) \leq \beta$, $a(x) \geq \beta$ and $a(x) = \beta$. Therefore, there are different canonical ways to represent a linear programming problem, one of which is the one we have already seen:

$$\min{c(x)} \quad \text{subject to } Ax \geq b$$

We may also express it as a maximization of the objective function:

$$\max{c(x)} \quad \text{subject to } Ax \leq b$$

Or either of them subject to a set of equalities:

$$\max{c(x)} / \min{c(x)} \quad \text{subject to } Ax = b$$

In all canonical forms variables are usually restricted to be positive or zero, which makes sense in most scenarios. In a future post I would like to revisit this subject, using one of the canonical forms to go a little deeper into the economical interpretation of each of the variables and constraints. But for now, we will go straight to the resolution.

Resolution

We have seen how to model an optimization problem using linear programming, but we still need to know how to solve it. Luckily, there are several algorithms that deal with these specific problems, one of the most widely known is simplex.

How simplex works deserves another blog post of its own, but for now lets just say that it solves most models incredibly fast. The problem of solving an LPP (linear programming problem) is known to be polynomial, which means that it can be solved within an acceptable timespan.

Needless to say, linear programming is an invaluable tool for modeling several real life scenarios, and has multiple applications within operations research. In future posts I would like to dwelve deeper into linear programming, which I will do if I have some spare time, but for now I will go on blogging within the scope of my thesis: integer linear programming.

Continuing with the tradition started by Beta two years ago here in Manas, I am now dedicating all my efforts to finish my thesis in order to obtain my MSc degree in Computer Science at FCEN-UBA. Having started it a few months ago, Manas generously started sponsoring my work in May, so I can deal with the last steps in the project and give it the finishing touch it deserves.

This work gives Manas Research division a very different direction than the one Beta gave it. Whereas his work was in the field of lambda calculus, my thesis is in operations research, integer linear programming to be more specific, dealing with a generalization of the graph coloring problem.

During these weeks I will be blogging about linear programming in general and the scope of my thesis, but for now I will upload the presentation I gave during the first days of June in the last ALIO/INFORMS joint meeting that took place in Buenos Aires so you can get a preview of what has been done so far.