Pricing via Shortest Path with Dual Values

In column generation for path-based multi-commodity flow, the pricing subproblem reduces to a shortest-path computation in a graph whose arc costs have been modified by the current dual values from the restricted master problem. This lesson covers computing reduced arc costs, finding the cheapest path, and deciding whether to add the resulting column to the RMP.

Step 1 of 157%

Tutorial

Pricing as a Shortest Path

In column generation for a path-based multi-commodity flow LP, the restricted master problem (RMP) has two families of constraints, each with its own dual variable:

A demand constraint $\sum_{p\in P_k} x_p = d_k$ for each commodity $k$ , with dual $\sigma_k$ .
A capacity constraint $\sum_{p} \delta_{ij}^p\, x_p \le u_{ij}$ for each arc $(i,j),$ with dual $\pi_{ij}\ge 0.$

For a candidate path $p$ from source $s_k$ to sink $t_k$ with arc cost $c_p = \sum_{(i,j)\in p} c_{ij},$ the reduced cost in the RMP is

\bar c_p \;=\; \sum_{(i,j)\in p} c_{ij} \;+\; \sum_{(i,j)\in p} \pi_{ij} \;-\; \sigma_k \;=\; \sum_{(i,j)\in p}\bigl(c_{ij}+\pi_{ij}\bigr) - \sigma_k.

Define the reduced arc cost

\tilde c_{ij} \;=\; c_{ij} + \pi_{ij}.

Then $\bar c_p = \sum_{(i,j)\in p}\tilde c_{ij} - \sigma_k.$ Minimizing $\bar c_p$ over all $s_k$ - $t_k$ paths is therefore a shortest-path problem in the graph with arc weights $\tilde c_{ij}.$ Because $c_{ij}\ge 0$ and $\pi_{ij}\ge 0,$ the reduced arc costs are non-negative, so Dijkstra's algorithm is applicable.

For instance, if arc $(i,j)$ has $c_{ij}=6$ and the current dual is $\pi_{ij}=2,$ then

\tilde c_{ij} = 6 + 2 = 8.