Constraints to avoid disjointed solutions in a MIP

Question

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?

Answer 1

It sounds like you want to enforce connectivity of an induced subhypergraph of a hypergraph with the blue nodes as the node set and a hyperedge for each path. You can do this by enforcing connectivity of an induced subgraph in the associated bipartite "incidence" graph with the blue nodes on the left, a node for each hyperedge on the right, and an edge if the blue node appears in the hyperedge.