Column generation for solving minimum cost multicommodity flow problem with additional edge disjoint constraints

Question

I'm working on an integer programming problem that's fundamentally a minimum cost multicommodity flow (MCMF) problem with additional constraints. I'm exploring the use of column generation to solve it, building upon the path-based formulation presented in this open-access article.

$min \sum_{k \in K}\sum_{p \in P(k)} c_p^ky_p^k $

$s.t:$

$\sum_{k \in K}\sum_{p \in P(k)} y_p^k\delta_{ij}^p \leqslant d_{ij}, \forall ij \in A $

$ \sum_{p \in P(k)} y_p^k = 1, \forall k \in K $

$ y_p^k \in \{0,1\}, \forall p \in P(k), \forall k \in K $

Where $y_p^k$ is a binary decision variable that equals $1$ if the commodity $k$ routed through path $p$ whose cost is $c_p^k$. $P(k)$ is the set of paths through which commodity $k$ can be routed. $\delta_{ij}^p$ is equal to $1$ if edge $ij$ is on path $p$, otherwise is equal to $0$. $d_{ij}$ is the capacity of edge $ij$.

My problem has the following unique characteristics:

• Commodity types: Commodities are partitioned into three distinct types: $K_{t_1}, K_{t_2}, K_{t_3}$, in other words: $K = K_{t_1} \cup K_{t_2} \cup K_{t_3}$.
• Type-exclusive edge usage: Flows belonging to different types must not share edges.

To enforce this edge exclusivity, I've introduced binary variables $V_{ij}^t$, $t \in \{t_1, t_2, t_3\}, \forall ij \in A$, indicating whether edge $ij$ is assigned to type $t$. The constraints are as follows:

1. Edge assignment constraint: $\sum_{t \in \{t_1, t_2, t_3\}} V_{ij}^t = 1, \forall ij \in A$

2. Flow compatibility constraint: $\sum_{k \in K_t} \sum_{p \in P(k)} \delta_{ij}^k y_p^k \leqslant V_{ij}^t d_{ij}, \forall K_t \in \{K_{t_1}, K_{t_2}, K_{t_3}\}, \forall ij \in A$

My questions are:

1. Is column generation still applicable to this modified problem structure?
2. If so, how do these additional constraints, particularly the edge assignment constraint (1), impact the pricing problem and other aspects of the column generation procedure?

Answer 1

Yes, column generation still applies. The edge assignment constraints do not contain $y$, so they do not directly affect the pricing problem for each commodity $k$, which is to find a negative reduced cost path for that commodity. The pricing problem is still a shortest path problem, but the arc costs should now be adjusted by the nonnegative dual value $-\beta_{ij}^{t_k}$ of the flow compatibility constraint, where $t_k$ is the type of commodity $k$. Explicitly, the cost of arc $(i,j)$ for subproblem $k$ is $c_{ij}^k+\pi_{ij}+\beta_{ij}^{t_k}$. The variables $V_{ij}^t$ are master-only, and the edge assignment constraint affect the subproblems indirectly through the duals on the other master constraints.

But the way, for the restricted master LP, you should relax $y$ to be nonnegative rather than $[0,1]$, as discussed in this recent question: Question on Column generation