A Common Mathematical Model of TSP Problems

Posted on Views: 13 Word count in article: 308 Reading time ≈ 1 mins.

The TSP problem usually requires finding a path with the minimum weight (or cost) that starts from the starting point, passes through all other nodes in sequence without repetition, and finally returns to the starting point

Parameter Description

Parameter Description
VV The collection of all nodes
nn Number of nodes
i,ji,j Node Number, i,j∈Vi,j \in V
cijc_{ij} The weight (or cost) of edge (i,j)(i,j)
xijx_{ij} 0-1 decision variable, where 1 means visiting edge (i, j) and 0 means not visiting edge (i, j)

Mathematical Model

Objective Function

Minimize the total weight (or cost):

Min:∑i∈V∑j∈Vcij⋅xijMin: \sum_{i \in V} \sum_{j \in V} c_{ij} \cdot x_{ij}

Constraints

(1) Each node can only be accessed once:

∑i∈Vxij=1,∀j∈V,i≠j\sum_{i \in V} x_{ij}=1, \forall j \in V, i \neq j

(2) Each node can only be left once:

∑j∈Vxij=1,∀i∈V,i≠j\sum_{j \in V} x_{ij}=1, \forall i \in V, i \neq j

(3) Subtour elimination constraint:

∑i,j∈Sxij≤∣S∣−1,2≤∣S∣≤n−1,S⊂V\sum_{i,j \in S} x_{ij} \le |S|-1, 2 \le |S| \le n-1, S \subset V

SS represents the node sets of the sub-loop.

(4) 0-1 decision variable:

xij∈{0,1}x_{ij} \in \{0,1\}

There are other forms of constraints for eliminating subtours. Here is the Miller-Tucker-Zemlin Subtour Elimination Constraint:

u1=12≤ui≤n,2≤i≤nui−uj+1≤(n−1)(1−xij),2≤i≠j≤nu_1=1 \\ 2 \le u_i \le n , 2 \le i \le n \\ u_i-u_j+1 \le (n-1)(1-x_{ij}), 2 \le i \neq j \le n

uiu_i represents the visit order of node ii. When ui<uju_i<u_j, it means that node ii is accessed earlier than node jj. The constant term (n−1)(n-1) provides sufficient slack when xij=0x_{ij}=0, and it does the same thing as the Big M.