I'm working on a graph problem via mathematical programming. I need to add a set of constraints to remove all cycles. I found a very interesting paper which suggests a way to do it using a set of linear constraints, please see https://arxiv.org/ftp/arxiv/papers/1202/1202.3713.pdf.
Here is what they did. Given a graph $G=(V,E)$, define a binary variable $I(W \rightarrow u)=1$ iff $W$ are the parents of $u$ in an optimal graph.
"These class of constraints rests upon the observation that any subset $C$ of vertices in a Directed Acyclic Graph (DAG) must contain at least one vertex who has no parent in that subset [It can have a parent in an external subset]. These are called cluster-based constraints and can be expressed as linear constraints":
Then, the follwoing equation will remove all cycles in the graph.
$$\forall C \subseteq V \quad \sum_{u \in C} \sum_{W: W\cap C =\emptyset} I\{W \rightarrow u\} \geq 1.$$
I have difficulty to underestand these set of inequalities. For instance, consider the graph $(1,2), (2,3), (3,4), (4,1), (5,1), (6,2), (7,3), (8,4)$. It seems to me that the set of equalities above does not remove the loop $1-2-3-4$. The author of this paper are quite expert in their domain. Hence, I assume that I misunderestood these set of inequalities :)
I would appreciate if someone gives a more intutive explanation, preferebly via an example.
Thanks a lot!!!
The key is that $W$ is a possible set of all "parents" (sources linked to) $u$. So the "parent sets" of nodes 1 through 4 are, respectively, {4, 5} (parents of 1), {1, 6}, {2, 7}, and {3, 8}. For the set $C = \{1,\dots,4\}$, no node in $C$ has a parent set disjoint from $C$; so for each $u\in C$ the inner summand is over an empty set of terms, and hence is zero.
There are simpler ways to remove cycles. If, in your model, $x_{ij}$ is a binary variable indicating that the arc $(i,j)$ was selected/is present, the constraint $$\sum_{i\in S, j\in S} x_{ij} \le |S|-1 \quad \forall S\subseteq V$$gets the job done. As with the constraints you asked about, a potential issue is that the number of constraints grows exponentially with the size of $V$. For a smaller approach (quadratic in the number of nodes), albeit one that produces a somewhat weaker relaxation, you might want to look at the Miller-Tucker-Zemlin constraints.