Minimum clique cover via MIP

Question

I have a general (undirected) graph with a set of nodes and a set of edges. I want to find a minimum clique cover of the graph, that is, a partition of the graph into the smallest number of cliques (a clique is a set of nodes where each pair of nodes is connected). I want to use an integer programming approach for this problem.

Can any one give me some hints or some references that use mixed integer linear programming for the minimum clique partition?

Thank you very much.

Answer 1

Edge clique cover

Let $G=(N,E)$, and let $C$ be an index set of candidate cliques. For example, you can take $C=\{1,\dots,|E|\}$. For $i\in N$ and $c\in C$, let binary decision variable $x_{i,c}$ indicate whether node $i$ is in clique $c$. For $(i,j)\in E$ and $c\in C$, let binary decision variable $y_{i,j,c}$ indicate whether edge $(i,j)$ is in clique $c$. For $c\in C$, let binary decision variable $z_c$ indicate whether clique $c$ is used. Then the problem is to minimize $\sum_c z_c$ subject to \begin{align} x_{i,c} &\le z_c \\ x_{i,c} + x_{j,c} -1 &\le y_{i,j,c} &&\text{if $(i,j)\in E$}\\ x_{i,c} + x_{j,c} &\le 1 &&\text{if $(i,j)\not\in E$}\\ y_{i,j,c} &\le x_{i,c} \\ y_{i,j,c} &\le x_{j,c} \\ \sum_c y_{i,j,c} &= 1 \end{align} Two remarks:

1. If you have an upper bound $\overline{z}$ on the optimal objective value, you can reduce the index set to $C=\{1,\dots,\overline{z}\}$.
2. If your solver does not already exploit symmetry, you might want to impose symmetry-breaking constraints like $z_c \le z_{c-1}$.

Node clique cover

This is equivalent to finding the chromatic number of the graph complement of $G$. With $x$ and $z$ defined as above, the problem is to minimize $\sum_c z_c$ subject to \begin{align} x_{i,c} &\le z_c \\ x_{i,c} + x_{j,c} &\le 1 &&\text{if $(i,j)\not\in E$}\\ \sum_c x_{i,c} &= 1 \end{align} You can get a formulation for chromatic number by changing $\not\in E$ to $\in E$ in the second constraint.