1
$\begingroup$

The Dantzig-Fulkerson ILP-formulation of the symmetric TSP is $$\min\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^n c_{ij}x_{\lbrace i,j\rbrace}\quad\text{s.t.}\\ \sum\limits_{j\ne i,\,j=1}^n x_{\lbrace i,j\rbrace}=2\quad i=1,\,\dots,\, n;\\ \sum\limits_{i\in Q}\sum\limits_{j\ne i,\,j\in Q}x_{\lbrace i,j\rbrace}\le|Q|-1\quad \forall Q\subsetneq \lbrace1,\,\dots,\,n\rbrace,\ |Q|\ge 2\\ x_{\lbrace i,j\rbrace}\in\lbrace 0,1\rbrace$$

Questions:

  • is it known that the $n$ degree-constraints for vertices be replaced with the single cardinality constraint $$\sum\limits_{i=1}^{n-1}\sum_{j=i+1}^n x_{\lbrace i,j\rbrace}=n$$ because the maximal number of edges that a cycle-free graph with $n$ vertices can contain is $n-1$?
  • what are the tradeoffs for the reduced number of constraints?
$\endgroup$

1 Answer 1

3
$\begingroup$

Don’t forget Johnson!

Although your proposed formulation is still valid, aggregating constraints yields a weaker linear programming relaxation. You can find fractional solutions that satisfy the aggregated (cardinality) constraint but violate at least one of the degree constraints. The net effect will typically be a larger search tree and a longer run time.

$\endgroup$
1
  • $\begingroup$ so being able to drop the degree constraints is only of negligible theoretical interest... $\endgroup$ Nov 14, 2021 at 14:20

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.