The two-commodity flow formulation is introduced by Baldacci et al. (2004). It is known for its good performance and providing a tight lower bound. I searched the literature, but couldn't find any study that expands this formulation on asymmetric digraphs. Do you think it is possible to expand this formulation on asymmetric digraphs? If not, why? If yes, do you know a study that did this already?


One way to do this is as follows: for each edge $(i,j)$ introduce binary variables $z_{ij}$ and $z_{ji}$ that indicate whether a vehicle travels from $i$ to $j$ or from $j$ to $i$, and add the constraint $z_{ij} + z_{ji} \le 1$.

Now $z_{ij} + z_{ji}$ is equal to 1 if edge $(i,j)$ is used in the solution and equal to 0 if edge $(i,j)$ is not used. You can now simply replace $\xi_{ij}$ by $z_{ij} + z_{ji}$. This follows from the fact that capacity is symmetric: it does not matter in which direction you travel, the load remains the same.

The above approach is explained in more detail in a paper of mine. I am not claiming that this is the only way or the best way to use this formulation in an asymmetric setting.

  • 1
    $\begingroup$ Thank you for your reply. Very interesting paper too. $\endgroup$
    – Mehdi
    Aug 8 '19 at 8:22

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.