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.


I believe it is a mistake to assume that new paths should be disjoint with existing paths. The master problem will deal with enforcement of disjointness within the selected paths. If you try to constrain new paths to be disjoint with previous paths, and one of your previous paths is not part of any optimal solution, it could keep out paths that should be.

The column generation problem will "price" paths according the dual solution of the (relaxed) master problem. The dual multipliers for the disjointness constraints will essentially serve to "discourage" inclusion of nodes to varying degrees. I think all you need for constraints in the subproblem are those guaranteeing a simple (loop free) continuous path from source to sink.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.