1
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ The general question would be if it is beneficial to construct start vectors for LPs that resemble the combination of thematically related variables like the $x_{ij}$ for degree constraints and the $u_i$ for connectivity by solving separate, dedicated LPs and then let the original LP take care of the "aligning", i.e. enter an utopia-vector into the "multi-objective" LP. $\endgroup$
    – Manfred Weis
    Commented Jan 2, 2022 at 11:12

0

Reset to default

You must log in to answer this question.