3
$\begingroup$

In the DFJ formulation of the symmetric TSP, the subtour elimination constraints are typically written as: $$\sum_{\{i,j\} \in E: \ i \in S, j \notin S} x_{ij} \geq 2, \qquad \forall S \subset V, \; 3 \leq |S| \leq |V|-1$$ where $V$ is the set of vertices.

It is sometimes pointed out that the number of these constraints can be reduced by observing that the constraints for $S$ and its complement $\bar{S}$ are the same. Therefore, one can write them as: $$\sum_{\{i,j\} \in E: \ i \in S, j \notin S} x_{ij} \geq 2, \qquad \forall S \subset V, \; 3 \leq |S| \leq \bigg \lfloor \frac{|V|}{2} \bigg \rfloor.$$

Although I've seen this kind of reduction in the number in a number of sources, I don't recall ever finding a similar observation (reduced formulation) for the ATSP -- at least not one that uses subsets with sizes not exceeding $\lfloor \frac{|V|}{2} \rfloor$. In my mind, unless I'm missing something, I'm thinking similar reasoning applies in the ATSP case. Namely, if we include constraints for all subsets of size $\leq \lfloor \frac{|V|}{2} \rfloor$, a subtour of size $> \lfloor \frac{|V|}{2} \rfloor$ will never occur since that implies that there exist other subtours whose size $\leq \lfloor \frac{|V|}{2} \rfloor$. In that case, can we write: $$\sum_{(i,j) \in A: \ i \in S, j \notin S} x_{ij} \geq 1, \qquad \forall S \subset V, \; 2 \leq |S| \leq \bigg \lfloor \frac{|V|}{2} \bigg \rfloor?$$

If so, is there a reason why the ATSP DFJ formulation is always presented in its more general form with almost all possible subsets? Of course, the number is still exponential (maybe it doesn't matter in a sense), but still surprised me that I could not find a reference that supported this.

Thanks for your help!

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.