If one doesn't want to introduce additional variables to the ILP of a TSP instance, one has to add exponentially many so-called subtour-elimination constraints; in practical calculations subtour-elimination constraints are added lazily, i.e. as subtours are encountered.
The number of subtour elimination constraints that are added after every iteration is $O(n)$.
Question:
if after an iteration in calculating the optimal tour via a sequence of ILPs $k$ subtours are encountered:
wouldn't it be more efficient to
- replace the $k$ subtour elimination constraints
- with the single "subtour gluing constraint"
that demands that summing over the variables that correspond to edges that are adjacent to two vertices from different subtours from the current set of subtours?
Addendum:
to clarify what kind of constraint is proposed I denote by $S_i(V_i,E_i)$ the subgraph induced by the $n_i$ vertices $V_i$ of the $i$-th subtour of the current iteration;
I further denote by $|S_i|$ the number of that subgraph's edges that are in the optimal solution of the next iteration.
With the above notation
- the classical subtour elimination constraints would be $|S_h|\,\lt\, n_h,\ h=1,\,\dots,\,k$ and
- the proposed subtour gluing constraint would be $$\sum\limits_{\lbrace i,j\rbrace: e_{ij}\ \in\ E(G)\,\setminus\,\bigcup\limits_{h=1}^k E_h}x_{ij}\quad\ge\quad k$$