Warm tip: This article is reproduced from stackoverflow.com, please click
cplex linear-programming mixed-integer-programming traveling-salesman

How to interpret sub tour elimination constraint in travelling salesman problem in cplex?

发布于 2020-06-27 21:08:54

I have written the following code:

enter image description here

How to interpret auxiliary constraints and sub tour elimination constraints in the following formulation?

enter image description here

Questioner
sudarsan vs
Viewed
40
分享
Erwin Kalvelagen 2020-04-11 01:01

The interpretation of the MTZ subtour elimination approach is actually quite simple. Assign numbers u(i) to each node in the order in which they are visited. The constraint

u(i) - u(j) + n x(i,j) <= n - 1

can be interpreted as 

u(j) >= u(i) + 1 - M*(1-x(i,j))

or 

x(i,j) = 1 ==>   u(j) >= u(i) + 1

If you have a subtour say 2-3-2 this cannot hold: 

2-3 means u(3) >= u(2)+1
3-2 means u(2) >= u(3)+1

As the whole tour should be allowed, we just drop the first node from this check.

Related issues

1
Julia
2
How to multiply multiple variables in a linear programming problem?
3
LP model does not give expected answer
4
Implementing a constraint based on previous variable's value in GNU Mathprog/AMPL
5
How can I define a set of linear constraints for the condition: "if x1 ≤ 0, then x2 ≤ 0"?
6
Non-optimal result from MIP program in Google OR Tools
7
Converting conditional constraints to linear constraints for Linear Programming
8
Multi-knapsack problem with aggregate objective function/objective with a soft limit
9
Why is MIP best bound infinite for this problem?
10
R OMPR package