0
$\begingroup$

Consider the Traveling Salesman Problem: Input: $n$ cities, distances $c_{ij}$ for each ordered pair $(i,j)$ of them.

Output: Find a shortest round tour visiting every city exactly once.

I came across the following ILP formulation, where we introduce a variable $x_{ij} \in \{0,1\}$ for each pair of cities $i,j$ where $x_{ij} = 1$ means arc $i,j$ is part of the tour. Then we have:

Minimize $$\sum_{1 \leq i,j \leq n} c_{ij} x_{ij}$$

Subject to $$\forall k = 1, \dots, n: \sum_{1 \leq i \leq n} x_{ik} = 1$$ $$\forall k= 1, \dots, n: \sum_{1 \leq j \leq n} x_{kj} = 1$$ $$\forall \subsetneq S \subsetneq \{1, \dots, n\}: \sum_{i,j \in S} x_{ij} \leq |S| -1 $$

While I understand the purpose of the first two constraints to make sure there is only one incoming and one outgoing edge per city, I do not understand the purpose of the third constraint. From what I read, this constraint is to make sure that solutions consisting of several disconnected tours are not possible - But how is this enforced by the third constraint and why are disconnected subtours not prevented by the first two constraints already? If we have two disconnected subtours, then at least one vertex must have an incoming edge but no outgoing edge, no?

$\endgroup$
4
$\begingroup$

Consider this example:

enter image description here

Every vertex has one incoming and one outgoing edge, so it is not prevented by the first two constraints. It is however prevented by the third constraint, as if you take any of the two connected components for $S$ it violates the inequality.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks! So the constraint is to prevent cycles? $\endgroup$ – securitymensch Feb 26 at 18:23
  • $\begingroup$ Yes, except for a cycle consisting of all vertices of course (S is a strict subset) as this is what you are looking for. $\endgroup$ – Tassle Feb 28 at 15:16

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.