1
$\begingroup$

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?
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Dec 28, 2023 at 2:40
  • $\begingroup$ @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. $\endgroup$
    – Sina_Alef
    Dec 28, 2023 at 8:46
  • $\begingroup$ 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 ? $\endgroup$
    – Kuifje
    Dec 31, 2023 at 15:32
  • $\begingroup$ @Kuifje the edge assignment constraint doesn't impose edge usage. It only restricts the number of flow types that the corresponding edge can have. $\endgroup$
    – Sina_Alef
    Jan 1 at 14:24

1 Answer 1

2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – abcd
    Dec 31, 2023 at 15:38
  • $\begingroup$ @abcd I adopted the convention of Section 3.1 in the paper, where the same approach is used for the $\le$ constraint $(6)$. $\endgroup$
    – RobPratt
    Dec 31, 2023 at 15:42
  • $\begingroup$ 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?) $\endgroup$
    – abcd
    Dec 31, 2023 at 16:12
  • $\begingroup$ 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. $\endgroup$
    – RobPratt
    Dec 31, 2023 at 16:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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