2
$\begingroup$

I know that it is common to branch on the flow on arcs to ensure intergrality when solving VRPs, but in which circumstances is valid to branch on the flow on edges instead of arcs? References to papers discussing this are welcome.

$\endgroup$

1 Answer 1

3
$\begingroup$

It really depends on the problem and on the formulation that is used. For example, in the following paper the authors compare different formulations for the CVRP, some of which are defined on arcs and some of which are defined on edges:

  • An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-Commodity Network Flow Formulation. R. Baldacci, E. Hadjiconstantinou, and A. Mingozzi, Operations Research 2004 52:5, 723-738. https://doi.org/10.1287/opre.1040.0111

In general, to justify branching on edges, you need to prove the following: when you obtain your final edge solution, you can turn it into a feasible arc solution with the same cost. In the case of symmetric VRP this is trivial: just traverse all your edges in the same direction. In the case of CVRP this is already tricky: the multi-commodity formulation, for example, propagates load based on the direction of the arc, so the constraint may not work correctly for edges, making it impossible to convert back into a feasible arc solution.

If it is not justified to branch on edges, but you really want to anyways, there are ways to deal with that. For example, I wrote a paper where we branch on edges to avoid symmetry to make the search more efficient. When an edge solution is found, we try to turn it into an arc solution. If that fails, we add a constraint to eliminate this edge solution, and continue the search.

  • Addressing Orientation Symmetry in the Time Window Assignment Vehicle Routing Problem. Kevin Dalmeijer and Guy Desaulniers. INFORMS Journal on Computing 2021 33:2, 495-510. https://doi.org/10.1287/ijoc.2020.0974
$\endgroup$
3
  • 1
    $\begingroup$ Thank you for your answer! Do you happen to know whether it is sufficient to branch on edges when solving the VRPTW with a set partitioning formulation? If it is not, do you know a paper showing that it is not suffient? $\endgroup$
    – gmn
    Apr 2 at 7:57
  • $\begingroup$ My guess is that it is sufficient to branch on edges when the costs are symmetric. To branch down, you remove both arcs. To branch up, you likely need a new constraint x_ij + x_ji = 1, and then you need to include those duals in the pricing problem. Section 3.1 in the second paper above goes into some of the implementation details. The main argument for why this works is that, eventually, you end up with disjoint undirected elementary paths. If this happens to correspond to fractional paths in both directions, you just pick one. I think this idea is quite common, but could not find a nice ref. $\endgroup$ Apr 3 at 20:15
  • $\begingroup$ Probably even works when the costs are asymmetric, because you can pick the best route at the end. $\endgroup$ Apr 3 at 20:23

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.