13.2.3.1. A "Better" ILP Formulation

The formulation of the multiway vertex cut problem provided in (13.3) and the analogous formulation of the multiway edge cut problem are based on the fact that the chosen cut must destroy all paths between any two terminals. The description of the multiway vertex cut or multiway edge cut problem at the beginning of Section 13.1.2 said that every connected component of \(G - C\) should contain at most one terminal, where \(C\) is the cut. Thus, an alternative formulation of the multiway edge cut problem is to compute a partition of the vertex set of \(G\) into \(k\) subsets \(V_1, \ldots, V_k\)—the vertex sets of the connected components of \(G - C\)—so that each such subset \(V_i\) contains exactly one terminal. W.l.o.g., we can assume that the terminal in \(V_i\) is \(t_i\). The cut \(C\) is then the set of edges \((u,v)\) such that \(u\) and \(v\) belong to different sets in this partition: \(u \in V_i\), \(v \in V_j\), and \(i \ne j\). You should be able to verify that every valid multiway edge cut \(C\) gives a partition of the vertices in \(G\) into \(k\) subsets \(V_1, \ldots, V_k\) such that each subset \(V_i\) contains only one terminal and, conversely, that for any such partition, the set of edges between vertices in different sets is a multiway edge cut. Thus, this is a correct formulation of the multiway edge cut problem.

How do we represent this partition of the vertex set of \(G\) into \(k\) subsets \(V_1, \ldots, V_k\)? We can assign a vector \(x_v = (x_{v,1}, \ldots, x_{v,k})\) to each vertex \(v \in G\) such that \(x_{v,i} = 1\) if and only if \(v \in V_i\). In particular, we require that exactly one entry \(x_{v,i}\) in this vector \(x_v\) is \(1\), and all other entries must be \(0\). In an ILP, this condition is easy to express as a set of linear constraints:

\[\begin{aligned} \sum_{i=1}^k x_{v,i} &= 1 && \forall v \in V\\ x_{v,i} &\in \{ 0, 1 \} && \forall v \in V, 1 \le i \le k. \end{aligned}\]

We also want each set \(V_i\) to contain exactly one terminal. As observed above, we can assume that the terminal in \(V_i\) is \(t_i\). This is also easy to express as a set of linear constraints:

\[\begin{aligned} x_{t_i,i} &= 1 && \forall 1 \le i \le k\\ x_{t_i,j} &= 0 && \forall 1 \le i, j \le k, i \ne j. \end{aligned}\]

A set of vectors \(\hat x_v\) satisfies these constraints if and only if it represents a partition of the vertex set of \(G\) into subsets \(V_1, \ldots, V_k\) such that each set \(V_i\) contains the terminal \(t_i\) and no other terminal. Thus, it represents a valid multiway edge cut

\[C = \{(u,v) \in E \mid u \in V_i, v \in V_j, i \ne j \}.\]

What remains to be done is to formulate the weight of this cut \(\sum_{e \in C} w_e\) as a linear objective function.

Consider any edge \((u,v) \in E\) and the vectors \(\hat x_u\) and \(\hat x_v\) corresponding to \(u\) and \(v\) in a solution \(\hat x\) that satisfies the constraints above. If \(u\) and \(v\) belong to the same set \(V_i\), then \(\hat x_u = \hat x_v\) and \(\bigl\|\hat x_u - \hat x_v\bigr\|_1 = 0\), where \(\|y\|_1 = \sum_{i=1}^k |y_i|\) denotes the \(L_1\)-norm of the vector \(y = (y_1, \ldots, y_k)\). If \(u\) and \(v\) belong to different sets—\(u \in V_i\) and \(v \in V_j\) with \(i \ne j\)—then the \(i\)th coordinate of \(\hat x_u - \hat x_v\) is \(1\), the \(j\)th coordinate is \(-1\), and all other coordinates are \(0\). Thus, \(\bigl\|\hat x_u - \hat x_v\bigr\|_1 = 2\). As a result, after imposing an arbitrary ordering on the vertices in \(G\), the following expression equals the weight of the cut \(C\) defined by the partition of \(V\) into subsets \(V_1, \ldots, V_k\):

\[\frac{1}{2} \cdot \sum_{u < v} w_{u,v} \cdot \bigl\|\hat x_{u} - \hat x_{v}\bigr\|_1.\]

Unfortunately, this is not a linear function because the definition of the \(L_1\)-norm of a vector involves taking absolute values. To turn this into a linear function, we need to introduce some auxiliary variables \(d_{u,v}\), one for each pair of vertices \(u\) and \(v\) with \(u < v\). We cannot impose the constraint that \(d_{u,v} = \|\hat x_u - \hat x_v\|_1\), but we can ensure that this is true for any optimal solution of the ILP. In particular, we impose the constraints

\[\begin{aligned} d_{u,v} &\ge \sum_{i=1}^k d_{u,v,i} && \forall u, v \in V, u < v\\ d_{u,v,i} &\ge x_{u,i} - x_{v,i} && \forall u, v \in V, u < v, 1 \le i \le k\\ d_{u,v,i} &\ge x_{v,i} - x_{u,i} && \forall u, v \in V, u < v, 1 \le i \le k. \end{aligned}\]

This ensures that in any feasible solution \(\bigl(\hat x, \hat d\bigr)\), we have

\[\hat d_{u,v,i} \ge \bigl|\hat x_{u,i} - \hat x_{v,i}\bigr|\]

and, thus,

\[\hat d_{u,v} \ge \sum_{i=1}^k \hat d_{u,v,i} \ge \sum_{i=1}^k \bigl|\hat x_{u,i} - \hat x_{v,i}\bigr| = \bigl\|\hat x_u - \hat x_v\bigr\|_1.\]

If we change our objective function to

\[\frac{1}{2} \cdot \sum_{u < v} w_{u,v} d_{u,v},\]

then no optimal solution \(\bigl(\hat x, \hat d\bigr)\) chooses \(\hat d_{u,v}\) larger than its lower bound \(\bigl\|\hat x_u - \hat x_v\bigr\|_1\), so \(\hat d_{u,v} = \bigl\|\hat x_u - \hat x_v\bigr\|_1\) for every optimal solution.

This gives the following ILP formulation of the multiway edge cut problem:

\[\begin{gathered} \text{Minimize}\ \frac{1}{2} \cdot \sum_{u < v} w_{u,v}d_{u,v}\\ \begin{aligned} \text{s.t. } d_{u,v} &\ge \sum_{i=1}^k d_{u,v,i} && \forall u,v \in V, u < v\\ d_{u,v,i} &\ge x_{u,i} - x_{v,i} && \forall u, v \in V, u < v, 1 \le i \le k\\ d_{u,v,i} &\ge x_{v,i} - x_{u,i} && \forall u, v \in V, u < v, 1 \le i \le k\\ \sum_{i=1}^k x_{v,i} &= 1 && \forall v \in V\\ x_{t_i,i} &= 1 && \forall 1 \le i \le k\\ x_{t_i,j} &= 0 && \forall 1 \le i, j \le k, i \ne j\\ x_{v,i} &\in \{ 0, 1 \} && \forall v \in V, 1 \le i \le k. \end{aligned} \end{gathered}\tag{13.8}\]

We introduced the variables \(d_{u,v}\) and \(d_{u,v,i}\) only to translate the more natural objective function

\[\frac{1}{2} \cdot \sum_{u < v} w_{u,v} \cdot \bigl\|\hat x_{u} - \hat x_{v}\bigr\|_1\]

into a linear objective function. Since an optimal solution \(\bigl(\hat x, \hat d\bigr)\) of (13.8) satisfies the condition \(\hat d_{u,v} = \bigl\|\hat x_u - \hat x_v\bigr\|_1\), \cref{eq:multiway-edge-cut-ilp} and the following non-linear constraint program have the same set of optimal solutions:

\[\begin{gathered} \text{Minimize}\ \frac{1}{2} \cdot \sum_{u < v} w_{u,v} \cdot \|x_u - x_v\|_1\\ \begin{aligned} \text{s.t. } \sum_{i=1}^k x_{v,i} &= 1 && \forall v \in V\\ x_{t_i,i} &= 1 && \forall 1 \le i \le k\\ x_{t_i,j} &= 0 && \forall 1 \le i, j \le k, i \ne j\\ x_{v,i} &\in \{ 0, 1 \} && \forall v \in V, 1 \le i \le k. \end{aligned} \end{gathered}\tag{13.9}\]

We can therefore reason about optimal solutions of this more natural constraint program and avoid specifying the values of the variables \(d_{u,v}\) and \(d_{u,v,i}\) in the corresponding optimal solutions of (13.8).

In (13.9), every variable \(x_{v,i}\) is constrained to be integral. If we relax this constraint, we obtain the following constraint program that is equivalent to the LP relaxation of (13.8):

\[\begin{gathered} \text{Minimize}\ \frac{1}{2} \cdot \sum_{u < v} w_{u,v} \cdot \|x_u - x_v\|_1\\ \begin{aligned} \text{s.t. } \sum_{i=1}^k x_{v,i} &= 1 && \forall v \in V\\ x_{t_i,i} &= 1 && \forall 1 \le i \le k\\ x_{t_i,j} &= 0 && \forall 1 \le i, j \le k, i \ne j\\ 0 \le x_{v,i} &\le 1 && \forall v \in V, 1 \le i \le k \end{aligned} \end{gathered}\tag{13.10}\]

The constraints

\[\begin{aligned} \sum_{i=1}^k x_{v,i} &= 1\\ 0 \le x_{v,i} &\le 1 && \forall 1 \le i \le k \end{aligned}\]

for every vertex \(v \in V\) have an elegant geometric interpretation: The vector \(x_v = (x_{v,1}, \ldots, x_{v,k})\) must be a point of the \(\boldsymbol{(k-1)}\)-dimensional simplex \(\boldsymbol{\Delta_k}\) in \(\mathbb{R}^k\), which is exactly the set of all points \(p = (p_1, \ldots, p_k)\) in \(\mathbb{R}^k\) that satisfy the condition that \(0 \le p_i \le 1\) for all \(1 \le i \le k\) and \(\sum_{i=1}^k p_i = 1\). Figure 13.1 shows the \(2\)-dimensional simplex \(\Delta_3\) in \(\mathbb{R}^3\).

Figure 13.1: Coming soon!

For \(1 \le i \le k\), the \(\boldsymbol{i}\)th unit vector in \(\mathbb{R}^k\) is the vector

\[e_i = (\underbrace{0,\ldots,0}_{i-1},1,\underbrace{0,\ldots,0}_{k-i}),\]

that is, the vector that has coordinate \(1\) in the \(i\)th dimension and coordinate \(0\) in any other dimension. The corners of \(\Delta_k\) are exactly the unit vectors \(e_1, \ldots, e_k\). The constraints

\[\begin{aligned} x_{t_i,i} &= 1\\ x_{t_i,j} &= 0 && \forall 1 \le j \le k, i \ne j \end{aligned}\]

for every terminal \(t_i\) then say that \(x_{t_i} = e_i\).

Thus, we can write the relaxation (13.10) of our constraint program even more succinctly as

\[\begin{gathered} \text{Minimize}\ w(x)\\ \begin{aligned} \text{s.t. } x_v &\in \Delta_k && \forall v \in V\\ x_{t_i} &= e_i && \forall 1 \le i \le k, \end{aligned} \end{gathered}\tag{13.11}\]

where we define

\[w(x) = \frac{1}{2} \cdot \sum_{u < v} w_{u,v} \cdot \| x_u - x_v \|_1.\]

For any integral feasible solution \(\tilde x\), \(w(\tilde x)\) is exactly the weight of the edges in the multiway edge cut defined by \(\tilde x\).