1

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?
Sina_Alef
  • 35
  • 3
  • To give you a better answer it would help if you provide a more precise problem definition. Eg.$q^k$ isn't used in your constraints and most of the parameters and variables in your second constraint are undefined. – Joris Kinable Dec 28 '23 at 02:40
  • @JorisKinable thank you for your attention. I included the whole problem definition. My assumption was that the problem definition is already available in the linked article, and reiterating the definition is redundant. Also, forget about $q^k$ , they did not have any effect. Therefore, I eliminated them. – Sina_Alef Dec 28 '23 at 08:46
  • Should the edge assignment constraint not be $\sum_t V_{ij}^t \le 1$ ? (instead of $=$). In other words, do you want every edge to be used at most once or exactly exactly once ? – Kuifje Dec 31 '23 at 15:32
  • @Kuifje the edge assignment constraint doesn't impose edge usage. It only restricts the number of flow types that the corresponding edge can have. – Sina_Alef Jan 01 '24 at 14:24

1 Answers1

2

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

RobPratt
  • 32,006
  • 1
  • 44
  • 84
  • When you refer to the "non negative dual value $-\beta_{ij}^{t_k}$", do you implicitly consider that you rewrote the "flow compatibility constaint" with as a $\ge$ constraint (changing the sign of $\beta_{ij}^{t_k}$ in the process)? Is not simply $\beta_{ij}^{t_k}$ that is non negative? – abcd Dec 31 '23 at 15:38
  • @abcd I adopted the convention of Section 3.1 in the paper, where the same approach is used for the $\le$ constraint $(6)$. – RobPratt Dec 31 '23 at 15:42
  • Ok, and does this convention seem perfectly ok to you? (is it not the dual variable without the minus sign that is non negative after rewriting the constraint as a "$\ge$" constraint?) – abcd Dec 31 '23 at 16:12
  • Yes, if you rewrite as $\ge$, the dual will be nonnegative, but then you need to change the sign from plus to minus in the arc cost. – RobPratt Dec 31 '23 at 16:33