# Constraints to avoid disjointed solutions in a MIP

Given an directed graph $$G= (N,E)$$, where $$N$$ is the set of nodes and $$E$$ is the set of all edges, each associated with a direction. $$G$$ is a connected graph but not necessarily a complete graph.

A path can start at any of the blue nodes, can contain one or more blue node depending on the graph connectivity and the edges direction, but must end at the destination in red. My graphs are relatively small, thus it is possible to enumerate all possible paths. Let $$P$$ be the set of all paths with no cycles. In the graph below 7 paths are possible: $$P = \{p_{(n_1dst)},p_{(n_2dst)},p_{(n_3dst)},p_{(n_1n_2dst)}, p_{(n_1n_3dst)}, p_{(n_2n_3dst)}, p_{(n_1n_2n_3dst)}\}$$.

I want to write a set of constraints that makes sure that in the final solution we obtain a path or a subset of paths such that there's at least one blue node in common with all other blue nodes in the selected paths or all blue nodes are in the same path.

For example, for the graph below a solution that contains $$p_{(n_1dst)}$$ and $$p_{(n_2n_3dst)}$$ is not feasible. The possible feasible solutions are if we use at least:

1. $$p_{(n_1n_2n_3dst)}$$ + additional paths
2. $$p_{(n_1n_2dst)}$$ and $$p_{(n_1n_3dst)}$$ + additional paths
3. $$p_{(n_1n_2dst)}$$ and $$p_{(n_2n_3dst)}$$ + additional paths
4. $$p_{(n_1n_3dst)}$$ and $$p_{(n_2n_3dst)}$$ + additional paths

If we define $$x_{p} \in \{0,1\}^{|P|}$$ as a binary variable that equals 1 if path $$p$$ is used, and 0 otherwise. The following constraints can be added:

$$c_1:$$ $$p_{(n_1n_2dst)} + p_{(n_1n_3dst)} + p_{(n_1n_2n_3dst)} \geq 1$$
$$c_2:$$ $$p_{(n_1n_2dst)} + p_{(n_2n_3dst)} + p_{(n_1n_2n_3dst)} \geq 1$$
$$c_3:$$ $$p_{(n_1n_3dst)} + p_{(n_2n_3dst)} + p_{(n_1n_2n_3dst)} \geq 1$$

if for example $$p_{(n_1n_2dst)} = 1$$ then $$c_1$$ and $$c_2$$ are respected, thus in $$c_3$$, either $$p_{(n_1n_3dst)}$$ or $$p_{(n_2n_3dst)}$$ or $$p_{(n_1n_2n_3dst)}$$ has to be selected.

While this work for graphs of size 3, I tried to generalize it in this way for larger graphs (size 4 and more): $$\sum_{r~\in~\Theta_{n}} x_{p} \geq 1, \forall~ n \in N$$, where $$\Theta_{n} = n \cup \Bigl\{ \bigcup_{k=1}^{k=|c^{'}|}$$ $$c^{'} \choose k$$ $$\Bigr\}, \forall n \in N$$, and where $$c^{'} = c \setminus \{n\}$$. I find for each node $$n$$ the combination of size 1 to $$|N|-1$$ of n with the remaining nodes without n. But this didn't work.

Does anyone has an idea on how to make this work, and if this problem has a name in the OR literature?

• Do you mean that you want every pair of selected paths to intersect in at least one blue node? Jul 19 at 19:37
• not necessarily for every pair of selected paths. Imagine you have a graph of 4 nodes where A --> B --> C --> D (A is connected only to B that is only connected to C that is only connected to D). Path $p_{AB}$ and $p_{CD}$ don't intersect in any node, but if one of the following paths $p_{BC}$ or $p_{ABC}$ or $p_{BCD}$ is used we have a feasible solution.
– CHE
Jul 19 at 20:11

• I hadn't come across hypergraphs before so I had to read about it. Following your idea I think the connectivity can be enforced for some graphs with special structure by adding the following constraint: $\sum_{p~\in~\Theta_{a}} x_{p} \geq 1 , \forall~ a = (u,v) \in \mathcal{A}$. Where $\mathcal{A}$ is the set of all connected arcs in $G$, and $\Theta_{a}$ is the set of all hyperedges containing the arc $a$. However, for a complete graph of size 4 this won't work.