This post will be about the Vehicle Routing Problem (VRP), a combinatorial optimization and integer programming problem which generalizes the famous Travelling Salesman Problem (TSP). To be even more specific, I'm making this post to discuss MTZ constraints, a set of sub-tour elimination constraints, in the Vehicle flow formulation of the VRP.
I tried to understand the ones given in the Wiki article but they are definitely wrong (as of this writing). Very many sources can be found on the internet but I was not able to understand any of them clearly. Turns out, those are not very hard to understand and I was able to make my own formulation. It goes like the following.
$u_i-u_j+Cx_{ij}\leq C-d_j$ $\forall i,j \in V \setminus \{0\}, i\ne j$ $s.t.$ $0<d_i \leq C$
$d_i\leq u_i \leq C$ $\forall i \in V \setminus \{0\}$
where $C$ is the capacity of the vehicle, $d_i$ is the demand of the $i$th city, and $x_{ij}$ is a binary variable that defines whether a tour happens from the $i$th city to the $j$th city or not (To avoid confusion, I've used the notations used in the Wiki article).
It is easy to see why this works. First, if there exists a sub-tour involving $k$ cities, then we can add the inequalities corresponding to those edges. The $u$ variables cancel each other and we will left with,
$0\leq -d_{i_1}-d_{i_2}-d_{i_3}-\cdots-d_{i_k}$
which is not possible because of the strictly positive constraint placed on the $d$ variables, thus proving every feasible tour of this formulation has exactly one sub-tour starting and ending at the 'origin' city.
To prove the existence of $u$ variables for all feasible solutions, first let's consider the case where not trip takes place from the $i$th city to the $j$th city. That is, $x_{ij}=0$. Then, the constraint corresponding to $x_{ij}$ becomes,
$0\leq (C-u_i)+(u_j-d_j)$
Both the bracketed terms are positive because of the constraints place on the $u$'s and thus the constraint becomes non-binding. On the other hand, let's consider the most interesting case of $x_{ij}=1$.
Now the $u$'s can be given a very nice interpretation. A particular $u_i$ can be interpreted as the cumulative demand delivered so far in tour upto (and including) city $i$. With this, we can see that easily see that the inequality becomes,
$-d_j+C\leq C-d_j$
which is trivially true. Hope you enjoyed this.
Until then,
Yours Aye,
Me
I tried to understand the ones given in the Wiki article but they are definitely wrong (as of this writing). Very many sources can be found on the internet but I was not able to understand any of them clearly. Turns out, those are not very hard to understand and I was able to make my own formulation. It goes like the following.
$u_i-u_j+Cx_{ij}\leq C-d_j$ $\forall i,j \in V \setminus \{0\}, i\ne j$ $s.t.$ $0<d_i \leq C$
$d_i\leq u_i \leq C$ $\forall i \in V \setminus \{0\}$
where $C$ is the capacity of the vehicle, $d_i$ is the demand of the $i$th city, and $x_{ij}$ is a binary variable that defines whether a tour happens from the $i$th city to the $j$th city or not (To avoid confusion, I've used the notations used in the Wiki article).
It is easy to see why this works. First, if there exists a sub-tour involving $k$ cities, then we can add the inequalities corresponding to those edges. The $u$ variables cancel each other and we will left with,
$0\leq -d_{i_1}-d_{i_2}-d_{i_3}-\cdots-d_{i_k}$
which is not possible because of the strictly positive constraint placed on the $d$ variables, thus proving every feasible tour of this formulation has exactly one sub-tour starting and ending at the 'origin' city.
To prove the existence of $u$ variables for all feasible solutions, first let's consider the case where not trip takes place from the $i$th city to the $j$th city. That is, $x_{ij}=0$. Then, the constraint corresponding to $x_{ij}$ becomes,
$0\leq (C-u_i)+(u_j-d_j)$
Both the bracketed terms are positive because of the constraints place on the $u$'s and thus the constraint becomes non-binding. On the other hand, let's consider the most interesting case of $x_{ij}=1$.
Now the $u$'s can be given a very nice interpretation. A particular $u_i$ can be interpreted as the cumulative demand delivered so far in tour upto (and including) city $i$. With this, we can see that easily see that the inequality becomes,
$-d_j+C\leq C-d_j$
which is trivially true. Hope you enjoyed this.
Until then,
Yours Aye,
Me
