Multi-commodity Network Flow: Convert a node-arc solution to an arc-path solution

Question

For a logistics optimization problem I am working on, the most natural expression of the problem is using a node-arc formulation of the MCNF. It is solved using an LP/MIP solver like CPLEX/Gurobi.

However, for understanding the solution, the arc-path formulation has certain attractive properties - it helps the user understand how different parts of the network's flows relate to each other. It is not possible, right now, to convert the formulation to arc-path.

I am looking for papers or tutorials which discuss how to convert a solution in node-arc form to a solution in arc-path form.

Answer 1

I don't know any references, but I can suggest a possible approach. For each commodity, generate a set of possible paths from the source of the commodity to the sink of the commodity. Let $x_a$ be the flow of that commodity on arc $a$ in your solution (I'm skipping commodity indices since we'll do each commodity separately) and let $H$ be a matrix with $H_{a,p} = 1$ if arc $a$ is on path $p$ and 0 if not. Solve \begin{align*} Hy & =x\\ y & \ge0 \end{align*} to get the path flows that in aggregate explain the arc flows. You can treat this as an LP if flows are divisible or IP if flows are discrete, with any objective function you like. A more complicated IP model would add a binary variable $z_p$ for each path $p$ and minimize $\sum_p z_p$, with constraints $y_p \le F z_p$ for all $p$, where $F$ is the total flow of the commodity out of its source. That would pick the simplest (least cardinality) set of paths needed to explain the arc flows.

One catch is that the problem might be infeasible if you do not generate enough paths, in which case you would need to go back and scrounge up more paths.

Answer 2

You can generate such a flow decomposition dynamically by treating each arc flow as an arc capacity and solving a maximum capacity s-t path problem to find a path. Then reduce the arc capacities along this path by the maximum flow value. Repeat until all arc capacities are $0$.

For a more general approach when you do not have a specified source and sink, see Section 3.5 of Network Flows, Ahuja, Magnanti, Orlin (1993).