Subtour elimination constraints - enumeration vs dynamically adding

Question

The classical constraints to prevent subtours in routing problems (i.e., to make sure every route is connected to a depot), are of the following form, $$ \sum_{(i,j) \in \delta(S)} x_{ij} \leq |S| - 1 \quad \forall S \subset V_C, $$ where $\delta(S)$ denotes all arcs connected to nodes in $S$ (and $V_C$ is the set of customer nodes), and $x_{ij}$ is the binary variable indicating whether edge $(i,j)$ is traversed.

Of course, adding a constraint for all $S \subset V_C$ is not feasible, so one usually separates such constraints/inequalities in a dynamic fashion (i.e, solving LP - separating inequality - resolve LP - separating - .. etc).

However, for $|S| = 2$ or $|S| = 3$ (i.e., all subsets of size 2, 3) the number of constraints is not too large. My question is the following: Is it worth the effort to enumerate such constraints for small sizes of $|S|$ and simply add those to the formulation before we start the solving process?

Answer 1

This has to depend on instance size. For a sports scheduling problem I worked on, it definitely made life easier to simply put in all the $|S| \le 3$ constraints (not exactly subtour, but very similar). But $n=30$ in that case. If you want to solve TSPs with, say, 1000 nodes, then $n^3$ is pretty big, and most of them are completely irrelevant. You will never hit the case where the subtour constraint on 3 widely separate points (with many in between) is relevant. But putting all of them in for trios that are sufficiently close may well work.

Answer 2

In my experience it is helpful to add the smallest sub tour constraints directly into the model formulation. You should play a bit with the exact size but I commonly add subtour constraints up to 4 customers.

You can also try to exclude some larger subtours that satisfy some conditions. For instance, select a random node $i$ and exclude the shortest cycle that starts/end at customer $i$ and visits $n$ other customers.