Skip to main content
added a top-level tag; see: https://meta.mathoverflow.net/questions/1457/why-are-mo-tags-formatted-as-they-are
Source Link
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40
added a exemplary choice for the binary $x_{ij}$ variables
Source Link
Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76

In the context of LP-formulations for the Traveling Salesman Problem the MTZ constraints prevent subtours via $n$ (i.e. effectively $n-1$) additional variables $$u_1=1\\2\le u_2,\,\dots ,\,u_n\le n\\ u_i -u_j \le (n-1)(1-x_{ij})-1$$

The constraints on the $u_i$ are linear and can thus be augmented with $n$ non-negative slack variables $s_i= (n-1)(1-x_{ij})- (u_i-u_j+1)$ that measure the cost of the choice of the $u_i$

Question:

which cost vector $\boldsymbol{c}\in\mathbb{R}^n$ for the "slack vector" $\boldsymbol{s}$ yields the "best" start-vector $\boldsymbol{u}$ of MTZ variables for the MTZ LP-formulation of a TSP-instance for $\boldsymbol{c}^T\boldsymbol{s}=\operatorname{min}$ if we take as the start vector for the $x_{ij}$ the binary variables of the lightest $2$-factor?

In the context of LP-formulations for the Traveling Salesman Problem the MTZ constraints prevent subtours via $n$ (i.e. effectively $n-1$) additional variables $$u_1=1\\2\le u_2,\,\dots ,\,u_n\le n\\ u_i -u_j \le (n-1)(1-x_{ij})-1$$

The constraints on the $u_i$ are linear and can thus be augmented with $n$ non-negative slack variables $s_i= (n-1)(1-x_{ij})- (u_i-u_j+1)$ that measure the cost of the choice of the $u_i$

Question:

which cost vector $\boldsymbol{c}\in\mathbb{R}^n$ for the "slack vector" $\boldsymbol{s}$ yields the "best" start-vector $\boldsymbol{u}$ of MTZ variables for the MTZ LP-formulation of a TSP-instance for $\boldsymbol{c}^T\boldsymbol{s}=\operatorname{min}$?

In the context of LP-formulations for the Traveling Salesman Problem the MTZ constraints prevent subtours via $n$ (i.e. effectively $n-1$) additional variables $$u_1=1\\2\le u_2,\,\dots ,\,u_n\le n\\ u_i -u_j \le (n-1)(1-x_{ij})-1$$

The constraints on the $u_i$ are linear and can thus be augmented with $n$ non-negative slack variables $s_i= (n-1)(1-x_{ij})- (u_i-u_j+1)$ that measure the cost of the choice of the $u_i$

Question:

which cost vector $\boldsymbol{c}\in\mathbb{R}^n$ for the "slack vector" $\boldsymbol{s}$ yields the "best" start-vector $\boldsymbol{u}$ of MTZ variables for the MTZ LP-formulation of a TSP-instance for $\boldsymbol{c}^T\boldsymbol{s}=\operatorname{min}$ if we take as the start vector for the $x_{ij}$ the binary variables of the lightest $2$-factor?

Post Undeleted by Manfred Weis
Post Deleted by Manfred Weis
Source Link
Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76

How to chose the start vector for the MTZ variables

In the context of LP-formulations for the Traveling Salesman Problem the MTZ constraints prevent subtours via $n$ (i.e. effectively $n-1$) additional variables $$u_1=1\\2\le u_2,\,\dots ,\,u_n\le n\\ u_i -u_j \le (n-1)(1-x_{ij})-1$$

The constraints on the $u_i$ are linear and can thus be augmented with $n$ non-negative slack variables $s_i= (n-1)(1-x_{ij})- (u_i-u_j+1)$ that measure the cost of the choice of the $u_i$

Question:

which cost vector $\boldsymbol{c}\in\mathbb{R}^n$ for the "slack vector" $\boldsymbol{s}$ yields the "best" start-vector $\boldsymbol{u}$ of MTZ variables for the MTZ LP-formulation of a TSP-instance for $\boldsymbol{c}^T\boldsymbol{s}=\operatorname{min}$?