HOME

Some combinatorial optimization problems

Table of Contents

Here we’ll mention some examples of modeling problems in combinatorics using linear programs with binary variables, that is, variables that are restricted to be either 0 or 1.

The subset sum problem

Given a list of numbers \(a_1, a_2, \ldots, a_n\) and a target sum \(s\), choose some of the numbers so that their sum is as close as possible to \(s\).

We can model this as an integer programming problem, with a binary variable \(x_i\) for each of the number. Here, “binary” means \(x_i\) is only allowed to take the values 0 or 1; which in LINDO is expressed by adding INT xi after the END of an LP. (Variables allowed to take any non-negative integral value are indicated with GIN xi —the G is for “general”.)

The variable \(x_i\) will be 1 or 0 according to wheter the number \(a_i\) is among the chosen ones. Then the sum of the chosen numbers is \(a_1 x_1 + \ldots + a_n x_n\). So we can model a few variants of this question as integer programs:

The price is right

If we want the sum to be as close as possible to \(s\), without going over, we can solve:

Maximize \(a_1 x_1 + \ldots + a_n x_n\)

subject to \[\begin{aligned} a_1 x_1 + \ldots + a_n x_n & \le s \\ x_1, \ldots, x_n & \in \{0,1\} \end{aligned} \]

Can we get within \(k\)?

Here we are only interested in whether the constraints are feasible, so we pick the objective function to be the constant \(0\): this makes sure the LP cannot be unbounded.

Maximize \(0\)

subject to \[\begin{aligned} a_1 x_1 + \ldots + a_n x_n & \le s + k \\ a_1 x_1 + \ldots + a_n x_n & \ge s - k \\ x_1, \ldots, x_n & \in \{0,1\} \end{aligned}\]

Notice that \(k\) is a parameter (i.e., a number we need to pick), not a variable in the LP.

What’s the closest we can get?

Just make \(k\) a variable too!

Minimize \(k\)

subject to \[\begin{aligned} a_1 x_1 + \ldots + a_n x_n & \le s + k \\ a_1 x_1 + \ldots + a_n x_n & \ge s - k \\ x_1, \ldots, x_n & \in \{0,1\} \end{aligned}\]

The partition problem

Given a list of numbers \(a_1, \ldots, a_n\), split them into two bunches such that the sums of the numbers in each bunch are as close as possible.

Minimize \(k\)

subject to \[\begin{aligned} a_1 x_1 + \ldots + a_n x_n & \le (a_1+\cdots+a_n)/2 + k \\ a_1 x_1 + \ldots + a_n x_n & \ge (a_1+\cdots+a_n)/2 - k \\ x_1, \ldots, x_n & \in \{0,1\} \end{aligned}\]

Shortcomings of these examples

The point of these easy examples is that many questions that seem very combinatorial and have initially nothing to do with linear programming can be encoded as linear program with binary variables. Of course, some encodings can be more clever that others! The ones above aren’t much good: one way to tell is that the relaxation of those problems is too easy, which is to say, the whole difficulty of the problem is packed into the constraint of the variables being 0 or 1.

For example, the LP for the partition problem always has the optimal solution \(k=0\), \(x_1=x_2=\ldots=x_n=0.5\), no matter what the \(a_i\) are!

Next we’ll take a look at a better example of encoding a combinatorial question as an integer linear program. It has more interesting constraints, capturing more of the problem and it’s relaxation is not trivial.

Graph coloring

A graph is simply a collection of vertices some pairs of which are connected by edges. A proper coloring of the graph is an assignment of a color to each vertex in such a way that any two vertices connected by an edge are assigned different colors (but vertices that are not connected directly by an edge may be assigned the same color). We can model proper colorings using linear constraints on binary variables as follows:

Let \(v_1, v_2, \ldots, v_n\) the vertices of the graph and let \(c_1, \ldots, c_m\) the available colors. Introduce a variable \(x_{ij}\) for every pair of a vertex \(v_i\) and color \(c_j\): \(x_{ij}\) will be 1 if \(v_i\) is assigned color \(c_j\) and 0 if not. In terms of these variables we can express the constraints of a proper coloring:

Each vertex must be assigned a color
For each \(i\), we have \(x_{i1} + x_{i2} + x_{im} = 1\).
Vertices connected by an edge must be assigned different colors
For each pair of vertices \(v_{i_1}\) and \(v_{i_2}\) that are connected by an edge, and for every color \(c_j\), we can express that \(v_{i_1}\) and \(v_{i_2}\) cannot both be color \(c_j\) via the constraint \(x_{i_1j} + x_{i_2j} \le 1\).

If we want to find out if a graph can be properly colored with some given number of colors, then these constraints are all we need. What if we want to know the minimum number of colors in a proper coloring? Well, if the graph has \(n\) vertices, and you have at least \(n\) colors available it is certainly possible to find a proper coloring: just give each vertex a different color! And by cleverly choosing an objective function we can find out the minimum numbers of colors needed (the so-called chromatic number of the graph).

Say the graph has 9 vertices, for example. Then 9 colors certainly suffice. For every coloring of the graph imagine forming the number whose digits are simply the number of times each color was used. For example, the number \(000120303 = 120303\) means that only four colors we actually used, one once, one twice, and two colors three times. Depending on how you number the colors, that same coloring could have gotten the numbers \(312030\), \(2331\), or \(1233\). Notice that \(1233\) is the smallest number that such a coloring (i.e., one using four colors, those numbers of times) can receive. Since numbers with more digits are always larger than numbers with fewer digits, if you look at the numbers associated to all colorings, the smallest one must correspond to a coloring with as few colors as possible! So, for our graph with 9 vertices, the objective function \(\sum_{j=1}^{9} \left( \sum_{i=1}^{9} x_{ij} \right) 10^{j-1}\) is minimized when the number of colors actually used is as small as possible.

For a graph with \(n\) vertices the same thing works, replacing those base \(10\) numbers with base \(n+1\) numbers, that is, \(\sum_{j=1}^{n} \left( \sum_{i=1}^{n} x_{ij} \right) (n+1)^{j-1}\) will be minimized at the same time as the number of colors is minmized. Of course, the minimum value of that objective function is not the minimum number of colors need to properly color the graph, but given an optimal solution \(x_{ij}\) you can easily figure out how many colors it used: just count for how many \(j\) at least one of the \(x_{ij}\) is 1.

LINDO LP generator

If you are reading this on the website, below you’ll a form that can generate these LPs in LINDO format, given a description of your graph. If you are reading this in PDF, the rest of this section will look empty.

Graph edges:

Check if graph can be colored with colors.

Find minimum number of colors needed.

Omar Antolín Camarena