A Question on A tutorial on column generation and branch-and-price for vehicle routing problems by Dominique Feillet

Question

I am reading A tutorial on column generation and branch-and-price for vehicle routing problems by Dominique Feillet to learn the column generation approach, but I have a problem. in section 3.3 entitled Subproblem I can't understand how Expression (23) is equivalent to Expression (22)?

The source considers a fleet of size $U$ and a directed graph $G = (V,A)$ with nodes $ V = \left \{v_0, \ldots, v_n \right \}$, where $v_0$ is the depot and the rest the customers. Every arc $(i,j)$ has an associated cost and time $c_{ij}$ and $t_{ij}$, respectively.

Then, the following notation is introduced to formulate the column generation model:

• $\Omega$ is the set of feasible routes
• $c_k$ is the cost of route $r_k \in \Omega$
• parameter $a_{ik} = 1$ if route $k$ visits customer $i$, 0 else
• parameter $b_{ijk} = 1$ if $k$ uses arc $(v_i,v_k)$, 0 else

With this, the standard column generation formulation for the VRPTW is stated as \begin{align} &\text{minimize} & \sum_{r_k \in \Omega} c_k \theta_k \\ &\text{s.t.} &\sum_{r_k \in \Omega} a_{ik} \theta_{k} &\ge 1, && v_i\in V \setminus \left \{ v_0 \right \}\\ &&\sum_{r_k \in \Omega} \theta_{k} &\le U \\ &&\theta_{k} &\in \mathbb{N}, && r_k \in \Omega \end{align}

Let $\lambda_0, \lambda_i$, be the dual variable associated to the fleet size constraint and for constraints related to visiting client $i$, respective, and $\lambda^*$ be an optimal solution to the dual of the restricted master program. The mentioned expressions (22) and (23) are the following:

Reduced cost subproblem: $$(22) \; c_k - \sum_{v_i \in V \setminus \left \{v_0 \right \} } a_{ik} \lambda^*_i - \lambda^*_0 < 0.$$ Equivalent problem: $$(23) \;\sum_{(v_i,v_j) \in A} b_{ijk}(c_{ij} - \lambda^*_i) < 0.$$

I 'm so appreciated if someone can help me.

Answer 1

Note that (as is asserted in the cited tutorial):

1. The cost of a route is the addition of the arcs that compose it: $c_k = \sum_{(v_i, v_j) \in A} b_{ijk}c_{ij}$
2. Relate $a_{ik}$ ($r_k$ visits customer $i$) with $b_{ijk}$ (route $k$ uses arc $(i,j)$): $a_{ik} = \sum_{v_j \in V: (v_i, v_j) \in A} b_{ijk}$

And the conditions (22) and (23) are equivalent because: \begin{align*} c_k - \sum_{v_i \in V \setminus \left \{v_0 \right \} } a_{ik} \lambda^*_i - \lambda^*_0 &\stackrel{1.}{=} \sum_{(v_i, v_j) \in A} b_{ijk}c_{ij} - \sum_{v_i \in V \setminus \left \{v_0 \right \} } a_{ik} \lambda^*_i - \lambda^*_0 \\ &\stackrel{2.}{=} \sum_{(v_i, v_j) \in A} b_{ijk}c_{ij} - \sum_{v_i \in V \setminus \left \{v_0 \right \} } \sum_{v_j \in V: (v_i, v_j) \in A} b_{ijk} \lambda^*_i - \lambda^*_0 \\ &= \sum_{(v_i, v_j) \in A} b_{ijk}c_{ij} - \sum_{(v_i, v_j) \in A: v_i \in V \setminus \left \{v_0 \right \}} b_{ijk} \lambda^*_i - \lambda^*_0 \\ &= \sum_{(v_i, v_j) \in A} b_{ijk}c_{ij} - \sum_{(v_i, v_j) \in A: v_i \in V \setminus \left \{v_0 \right \}} b_{ijk} \lambda^*_i - \sum_{v_j \in V - v_0} b_{0jk} \lambda^*_0 \\ &= \sum_{(v_i, v_j) \in A} b_{ijk}c_{ij} - \sum_{(v_i, v_j) \in A} b_{ijk} \lambda^*_i \\ &= \sum_{(v_i, v_j) \in A} b_{ijk}( c_{ij} - \lambda^*_i) \end{align*} where we used the fact that $\sum_{0jk} = 1$ for every feasible route $r_k$.