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?
Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .