1
$\begingroup$

I'm currently working on a special variation of the Multi-Commodity flow problem. My goal is to solve this variation via column generation, because the graph can become very large.

Description

Given...

  • a directed, acyclic Graph $G = (V, A)$
  • a set of commodities $\mathcal{K} = \{ k_1, k_2, \ldots, k_n \}$
  • a source $s_k$ and destination $t_k$ for each commodity
  • costs $c_{i, j}$ for each edge $(i, j) \in \mathcal{A}$
  • a set of special "group edges" $A_G \subseteq A$

... my goal is to minimize the sum of costs over all commodities, i.e., I want to find a minimum-cost flow. The twist is that the edges in the set $A_G$ are cheaper, but if a commodity chooses such a discounted edge, another commodity must use this edge as well. All other edges do not have a capacity limit.

Model

My current model (path formulation) looks like this:

$$ \begin{align} &\min &\sum_{k=1}^n \sum_{p \in P_k} c(p) \cdot \lambda_p^k \\ &\text{s.t.} &\sum_{p \in P_k} \lambda_p^k &= 1 &&\forall k \in \mathcal{K} \\ && \sum_{k=1}^n \sum_{p \in P_k} \delta^p_{u, v} \cdot \lambda^k_p &\leq 2 \cdot y_{u, v} && \forall (u, v) \in A_G \\ && \sum_{k=1}^n \sum_{p \in P_k} \delta^p_{u, v} \cdot \lambda^k_p &\geq 2 \cdot y_{u, v} && \forall (u, v) \in A_G \\ &&\lambda_p^k &\in \{ 0, 1\} && \forall k \in \mathcal{K}, \forall p \in P_k \\ &&y_{u, v} &\in \{ 0, 1 \} && \forall (u, v) \in A_G \end{align} $$

Where $\lambda_p^k = 1$ if path $p$ is selected for commodity $k$, $y_{u, v} = 1$ if group edge $(u, v)$ is being used. The parameter $\delta^p_{u, v} \in \{ 0, 1 \}$ indicates whether edge $(u, v)$ is part of path $p$. The first constraint is the usual convexity constraint. The second and third constraints force two commodities to traverse a group edge if the variable $y$ is $1$, i.e., if the edge is in use. The set $P_k$ is the set of all generated paths for commodity $k$. At the moment I'm trying to solve this problem via a branch and price approach (I branch on the $y$ variables), the integrality constraints for $\lambda$ are relaxed. I start with a very restricted set of paths and solve a shortest path problem for each commodity at every node in the tree to generate new columns. The weight of each group edge in the graph is computed via $c_{u, v}' = c_{u, v} - \alpha_{u, v} + \beta_{u, v}$, where $\alpha_{u, v}$ and $\beta_{u, v}$ correspond to the dual values of the group edge constraints ($\leq$ and $\geq$ respectively.)

My questions are:

  1. Is column generation or a column generation approach even applicable to this variation and is the pricing problem still a shortest path problem? I'm not sure how to deal with the $y$ variables in the reduced cost computation, because there is a variable on the right hand side of the two edge constraints.
  2. Is my formula to adjust the edge weights correct?
  3. Is there some way to get rid of the binary variable $y$? My current implementation in SCIP takes literally forever on small instances. One problem I see is that if the graph has a lot of group edges, all commodities can use such a cheap edge by setting $y = 0.5$, resulting in a lot of branching. This also means that the first LP solve at the root node has an extremely small objective value that can never be achieved.

Thanks!

$\endgroup$
4
  • $\begingroup$ Just to be clear, a "group" edge must carry either nothing or exactly two commodities (as opposed to at least two commodities)? $\endgroup$
    – prubin
    Commented Jun 21 at 21:48
  • $\begingroup$ @prubin exactly! :D. Either nothing or exactly two. $\endgroup$
    – jatsqi
    Commented Jun 21 at 21:52
  • $\begingroup$ So is there some reason why you have two inequality constraints to enforce that as opposed to one equality constraint? $\endgroup$
    – prubin
    Commented Jun 21 at 22:47
  • $\begingroup$ No reason in particular. I experimented with some BIG-M constraints before, so it could be a left-over from that. $\endgroup$
    – jatsqi
    Commented Jun 23 at 15:46

1 Answer 1

2
$\begingroup$

First note that you can replace the pair of inequality constraints with a single equality constraint.

  1. Yes, column generation with a shortest path subproblem applies here. The $y$ variable is a master-only variable that does not directly affect the reduced cost calculation.
  2. Partially correct. You need to account for the dual of the convexity constraint. In the current form of the master problem, you would also need to account for the dual for the upper bound on $\lambda$. A better approach is to omit the upper bound, which is already implied by the convexity constraint. See Variable bounds in column generation. Also, if you use an equality instead of two inequalities, replace the pair of dual variables with one.
  3. I don't see a way. Your business rule requires a disjunction ($0$ or $2$). But to strengthen the master formulation, you might impose some bounds on $\sum_{(u,v)\in A_G} y_{u,v}$, perhaps obtained by solving an auxiliary problem to minimize or maximize this sum. Such constraints that involve only $y$ do not affect the pricing problem.
$\endgroup$
4
  • $\begingroup$ Thanks! I impose no upper bound on the $\lambda$ variables, maybe I explained it poorly... But thanks for the link, was an interesting read nonetheless! With the equality constraint (instead of $\leq$ and $\geq$), the new edge weight would be $c_{u, v} - \gamma_{u, v}$, where $\gamma$ is the dual of the equality constraint, right? $\endgroup$
    – jatsqi
    Commented Jun 23 at 15:49
  • $\begingroup$ Yes, and you also need to account for the dual variable of the convexity constraint. $\endgroup$
    – RobPratt
    Commented Jun 23 at 15:56
  • $\begingroup$ But only when computing the reduced costs of the variable, right? I'm not sure how to account for that dual when computing the shortest path.. $\endgroup$
    – jatsqi
    Commented Jun 23 at 16:08
  • $\begingroup$ Let $\pi_k$ be the dual variable for the convexity constraint. For each commodity $k$, you want to find a path $p$ with reduced cost $c(p)-\pi_k-\gamma_{u,v}<0$. You can use arc weight $c_{u,v}-\gamma_{u,v}$ for the shortest path subproblem and then check whether the resulting shortest path distance is $<\pi_k$. $\endgroup$
    – RobPratt
    Commented Jun 23 at 16:20

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.