# Solving Disjoint verteces paths problem using column generation

I am faced with the following integer optimization problem which I am trying to solve using column generation:

Given is a digraph $G(V,A)$ with a source and sink node ($s, t$). Each path has a probability of succeeding, call it $r_p$ $\forall p \in PATHS$. The number of paths is huge for most instances obviously. The problem is now to select a set of $\textit{disjoint}$ paths such that the total reliability is maximized. The paths selected must be disjointed, that is each node can only be part of one path in the solution.

An IP-formulation for the problem is not hard to find, I'd say:

$\max \sum_{p \in P} \ r_p \cdot z_p \\ s.t: \sum_{p\in P} \alpha_{ip} z_p \leq 1 \ \ \forall i \in V \setminus\{s,t\}$.

Here $z_p$ is a binary variable representing whether or not path $p$ is part of the solution. $a_{ip}$ indicates if node $i$ is part of path $p$ or not and is a parameter.

I suppose this is a correct formulation of the problem, moreover, such a formulation is typically well suited to solve using column generation. However I am struggling to find the corresponding $\textit{pricing problem}$. If I am right, in the pricing problem we are searching for a column to add to the restricted master problem whose corresponding dual constraint is violated (or equivalently, whose reduced cost is negative?). So in this case we are looking to construct a path that is disjoint with the already selected paths that violates a dual constraint. So my attempt to write down the pricing problem was the following:

Call $a_i = 1$ iff vertex $i$ is in the path and $0$ else. Given the dual variables' value $\boldsymbol{y}$, the pricing problem is:

$\min \sum_{i \in V \setminus \{s,t\}} a_i \cdot y_i - r_p \\ s.t. \cdots$

And that's where I get stuck (if all the above was correct)... . I just can't seem to figure out what the constraints would look like to construct a path that is disjoint with the already selected paths using the indicator variable $a_i$ for each vertex.