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.