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.

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.