3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could you write the expressions and some context regarding the variables and parameters? (for the ones among us who don't have access to the publication) $\endgroup$ – dhasson Aug 12 at 16:21
  • $\begingroup$ in this part, it is said that the subproblem reduces to an elementary shortest path problem with resource constraints (ESPPRC). $\endgroup$ – Bhr Aug 12 at 21:54
5
$\begingroup$

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$.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.