# Subtour elimination constraints - enumeration vs dynamically adding

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?

• I don't know whether it is useful to add them immediately for small set sizes. It really depends on the interaction with every other part of the solver, e.g. branching rules and other inequalities. I will point out that in one my papers, I added similar constraints for all subsets of size 3 and it was solved fine. Also, "subtour elimination" for 2 and 3 vertices are useful in early work on pricers for vehicle routing problems. See the k-cycle elimination pricing algorithms. Jun 2 '19 at 7:20
• When you say "worth it", do you mean from the point of view of solve time, or from the point of view of the person coding it? I assume enumerating them all is a lot easier to code than writing a dynamic procedure so there's a tradeoff there too. Jun 2 '19 at 11:16
• Your notation $\delta(S)$ looks strange to me. Usually $\delta(S)$ is the set of edges in an undirected graph that have exactly one endpoint in $S$, however your problem seems to be directed. Also, do you want both endpoints of the edge to belong to $S$? In this case, I would use something like $E(S)$. Jun 4 '19 at 20:10
• You are probably right as I typed this from my phone :) I will change if needed tomorrow! Jun 4 '19 at 23:54

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