9
$\begingroup$

In many of vehicle routing problems variant (VRP), which can be formulated using MIPs, to avoid creating sub tour, we need to use sub tour elimination constraints (SEC). One of the known SEC is (I also know there are other types):

\begin{equation} u_{k}-u_{l}+|H| z_{k l} \leq|H|-1, \quad \forall k, l \in H, l \neq 1, l \neq k \end{equation}

What is interesting is that, in some of MIP models, these constraints are removed and replaced by other constraints.

I would like to know, is there any principle to replace such constraints with other inequalities and also any guarantee to do better performance using them?

$\endgroup$
5
$\begingroup$

The inequalities you have included in your post are the so-called MTZ SEC's which are known to be very weak. That is, they do not provide a very tight approximation of the convex hull of integer feasible solutions. There are tons of papers providing polynomial-sized sets of SEC's (see for instance Bektaş and Gouveia (2014)1 for stronger versions of the MTZ or Letchford and Salazar-González (2019)2 for (multi-)commodity flow-based formulations of the SEC's).

However, in practice, for problems consisting of more than say 20-30 customers, it usually works better to separate stronger SEC's from families of inequalities of exponential sizes. For example, for the CVRP, there is the set of "rounded capacity inequalities" given by \[ \sum_{i\in S}\sum_{j\not\in S}z_{ij} \geq \left\lceil \frac{\sum_{i\in S}q_i}{Q}\right\rceil,\qquad \forall S\subseteq \{1,\dots,n\} \] where $q_i$ is the demand of customer $i$ and $Q$ is the capacity of the vehicles (for information on the strength of different types of SEC's you can take a look at the very nice paper by Letchford and Salazar-González (2006))3. I believe that the state-of-the-art solvers for vehicle routing problems combine the agility of strong cutting planes with the strength of the LP bound obtained from the relaxation of a set-partitioning based formulation of the VRP in question.


References

[1] Bektaş, T., Gouveia, L. (2014). Requiem for the Miller-Tucker-Zemlin subtour elimination constraints? European Journal of Operational Research. 236(3):820-832.

[2] Letchford, A. N., Salazar-González, J-J. (2019). The Capacitated Vehicle Routing Problem: Stronger bounds in pseudo-polynomial time. European Journal of Operational Research. 272(1):24-31.

[3] Letchford, A. N., Salazar-González, J-J. (2006). Projection results for vehicle routing. Mathematical Programming. 105(2-3):251-274.

$\endgroup$
  • $\begingroup$ Thanks for your useful reply. The thing I encountered with it is, In some variant of VRP (specifically CVRP) SEC's are replaced by other constraints which do not similar to standard SEC's. As you mentioned they may not provide a very tight approximation. Therefore, I'm interested to know is there any procedure to solve the problem without using any type of standard SEC? $\endgroup$ – A.Omidi Jan 10 at 10:23
  • $\begingroup$ I think that an answer depends very much on what you consider to be “standard SEC’s”. I usually go with a one commodity flow formulation resembling the Gawish and Graves formulation to start out with, and if that works, I stop there. $\endgroup$ – Sune Jan 10 at 11:12
  • $\begingroup$ Thanks so much. Please, see this link. In this model, I can not see any standard SEC, instead, it is replaced by other constraints (If I'm wrong, pls. correct me). however, this formulation can not be used for the large real application, because, some of its constraints are week. My question is, how can I use such reformulation to remove SEC? $\endgroup$ – A.Omidi Jan 10 at 12:18
  • 2
    $\begingroup$ Constraints 2.20e and 2.20f are exactly SECs of the one commodity flow type $\endgroup$ – Sune Jan 10 at 14:35
  • $\begingroup$ Many thanks for your advice. I think I'm a bit confused about that. I will check it again and will ask the question if I have any issue. thanks once again. $\endgroup$ – A.Omidi Jan 10 at 20:04

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.