14
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$ – Edward Lam Jun 2 '19 at 7:20
  • $\begingroup$ 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. $\endgroup$ – LarrySnyder610♦ Jun 2 '19 at 11:16
  • $\begingroup$ 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)$. $\endgroup$ – Austin Buchanan Jun 4 '19 at 20:10
  • $\begingroup$ You are probably right as I typed this from my phone :) I will change if needed tomorrow! $\endgroup$ – Albert Schrotenboer Jun 4 '19 at 23:54
12
$\begingroup$

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.

Improve this answer
$\endgroup$
4
$\begingroup$

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.

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.