The MTZ formulation of the TSP is: (1) X xij = X j xji = 1 ∀i, j (2) ui − uj + 1 ≤ (n − 1)(1 − xij ) ∀i 6= 1, ∀j 6= 1, i 6= j. where the xij are binary variables for all (i, j) ∈ A, and the ui are continuous variables for i = 2, . . . , n. Consider the following statement: • If x represents a tour, then the only feasible value of the ui variables for i = 2, . . . , n is the position of city i in the tour. If this statement is true, then prove it. If it is not true, then modify it to make it true, and prove that it is true after the modification. 1
© Copyright 2024 ExpyDoc
