= Subtour elimination constraints
{title2=$\sum_{i,j\in S,\ i\ne j}x_{ij}\leq |S|-1$}
Binary arc variables with one outgoing and one incoming arc at each vertex describe a <cycle cover of a directed graph>. For every nonempty proper vertex subset $S$, the displayed inequality forbids a directed cycle confined to $S$. Together these inequalities make the cycle cover one <Hamiltonian cycle>. They can be generated as violated cuts or used in <branch and bound>, rather than all being stored initially.
Back to article page
