p12 | Traveling Salesman Problem (TSP)

See also

This problem is sourced from EvoCut [2].

Note

• The problem implicitly assumes more than two cities (\(n > 2\)).

NP-hard: yes

Description

The Traveling Salesman Problem (TSP) aims to find the shortest cycle in a graph that visits every node exactly once.

Formulations

Formulation a (valid)

See also

This formulation is sourced from EvoCut [2].

Note

• This is the MTZ formulation of the TSP from v1 of Yazdani et al. [2].

Parameters

Name	Description	Type	Shape
n	Number of cities	integer	scalar
c	Travel cost from city \(i\) to city \(j\)	continuous	[n, n]

Variables

Name	Description	Type	Shape / Indices
x	\(1\) if the tour goes directly from city \(i\) to city \(j\), \(0\) otherwise	binary	[n, n]
u	MTZ position of city \(i\) in the tour	continuous	[n]

Assumptions

Description	Formulation	Implicit
There must be at least two cities to form a tour.	\(n \geq 2\)	yes

Constraints

• Each city has exactly one outgoing arc in the tour.

  \[ \sum_{j \in V,\, j \neq i} x_{ij} = 1 \quad \forall i \in V \]

• Each city has exactly one incoming arc in the tour.

  \[ \sum_{i \in V,\, i \neq j} x_{ij} = 1 \quad \forall j \in V \]

• MTZ subtour elimination constraint.

  \[ u_i - u_j + n \times x_{ij} \leq n - 1 \quad \forall i, j \in V \setminus \{0\},\; i \neq j \]

• Depot position is fixed to \(1\) to anchor the tour ordering.

  \[ u_0 = 1 \]

• Lower bound on MTZ position: each non-depot city’s position is at least \(2\).

  \[ u_i \geq 2 \quad \forall i \in V \setminus \{0\} \]

• Upper bound on MTZ position: each city’s position is at most \(n\).

  \[ u_i \leq n \quad \forall i \in V \]

• No self-loops: a city cannot have an arc to itself. (implicit)

  \[ x_{ii} = 0 \quad \forall i \in V \]

Objective

Minimize the total travel cost of the Hamiltonian cycle.

\[ \min \sum_{i \in V} \sum_{j \in V,\, j \neq i} c_{ij} \times x_{ij} \]

Formulation b (valid)

See also

This formulation is sourced from EvoCut [2] (version: 1, name: EC1).

Note

• This is the MTZ formulation of the TSP from v1 of Yazdani et al. [2] augmented with acceleration cut EC1.

Parameters

Name	Description	Type	Shape
n	Number of cities	integer	scalar
c	Travel cost from city \(i\) to city \(j\)	continuous	[n, n]

Variables

Name	Description	Type	Shape / Indices
x	\(1\) if the tour goes directly from city \(i\) to city \(j\), \(0\) otherwise	binary	[n, n]
u	MTZ position of city \(i\) in the tour	continuous	[n]

Assumptions

Description	Formulation	Implicit
There must be at least two cities to form a tour.	\(n \geq 2\)	yes

Constraints

• Each city has exactly one outgoing arc in the tour.

  \[ \sum_{j \in V,\, j \neq i} x_{ij} = 1 \quad \forall i \in V \]

• Each city has exactly one incoming arc in the tour.

  \[ \sum_{i \in V,\, i \neq j} x_{ij} = 1 \quad \forall j \in V \]

• MTZ subtour elimination constraint.

  \[ u_i - u_j + n \times x_{ij} \leq n - 1 \quad \forall i, j \in V \setminus \{0\},\; i \neq j \]

• Depot position is fixed to \(1\) to anchor the tour ordering.

  \[ u_0 = 1 \]

• Lower bound on MTZ position: each non-depot city’s position is at least \(2\).

  \[ u_i \geq 2 \quad \forall i \in V \setminus \{0\} \]

• Upper bound on MTZ position: each city’s position is at most \(n\).

  \[ u_i \leq n \quad \forall i \in V \]

• No self-loops: a city cannot have an arc to itself. (implicit)

  \[ x_{ii} = 0 \quad \forall i \in V \]

• Depot-Exit Position Bound (EC1): if the tour leaves the depot directly to city \(j\), then \(j\) is positioned at most second in the ordering.

  \[ u_j \leq 2 + (n-2)(1 - x_{0j}) \quad \forall j \in V \setminus \{0\} \]

Objective

Minimize the total travel cost of the Hamiltonian cycle.

\[ \min \sum_{i \in V} \sum_{j \in V,\, j \neq i} c_{ij} \times x_{ij} \]

Formulation c (valid)

See also

This formulation is sourced from EvoCut [2] (version: 1, name: EC2).

Note

• This is the MTZ formulation of the TSP from v1 of Yazdani et al. [2] augmented with acceleration cut EC2.

Parameters

Name	Description	Type	Shape
n	Number of cities	integer	scalar
c	Travel cost from city \(i\) to city \(j\)	continuous	[n, n]

Variables

Name	Description	Type	Shape / Indices
x	\(1\) if the tour goes directly from city \(i\) to city \(j\), \(0\) otherwise	binary	[n, n]
u	MTZ position of city \(i\) in the tour	continuous	[n]

Assumptions

Description	Formulation	Implicit
There must be at least two cities to form a tour.	\(n \geq 2\)	yes

Constraints

• Each city has exactly one outgoing arc in the tour.

  \[ \sum_{j \in V,\, j \neq i} x_{ij} = 1 \quad \forall i \in V \]

• Each city has exactly one incoming arc in the tour.

  \[ \sum_{i \in V,\, i \neq j} x_{ij} = 1 \quad \forall j \in V \]

• MTZ subtour elimination constraint.

  \[ u_i - u_j + n \times x_{ij} \leq n - 1 \quad \forall i, j \in V \setminus \{0\},\; i \neq j \]

• Depot position is fixed to \(1\) to anchor the tour ordering.

  \[ u_0 = 1 \]

• Lower bound on MTZ position: each non-depot city’s position is at least \(2\).

  \[ u_i \geq 2 \quad \forall i \in V \setminus \{0\} \]

• Upper bound on MTZ position: each city’s position is at most \(n\).

  \[ u_i \leq n \quad \forall i \in V \]

• No self-loops: a city cannot have an arc to itself. (implicit)

  \[ x_{ii} = 0 \quad \forall i \in V \]

• Depot-Entry Position Bound (EC2): if the tour returns to the depot from city \(i\), then \(i\) is positioned last in the ordering.

  \[ u_i \geq n - (n-2)(1 - x_{i0}) \quad \forall i \in V \setminus \{0\} \]

Objective

Minimize the total travel cost of the Hamiltonian cycle.

\[ \min \sum_{i \in V} \sum_{j \in V,\, j \neq i} c_{ij} \times x_{ij} \]

Formulation d (invalid)

See also

This formulation is sourced from EvoCut [2] (version: 1, name: EC3).

Note

• This is the MTZ formulation of the TSP from v1 of Yazdani et al. [2] augmented with acceleration cut EC3.

Parameters

Name	Description	Type	Shape
n	Number of cities	integer	scalar
c	Travel cost from city \(i\) to city \(j\)	continuous	[n, n]

Variables

Name	Description	Type	Shape / Indices
x	\(1\) if the tour goes directly from city \(i\) to city \(j\), \(0\) otherwise	binary	[n, n]
u	MTZ position of city \(i\) in the tour	continuous	[n]

Assumptions

Description	Formulation	Implicit
There must be at least two cities to form a tour.	\(n \geq 2\)	yes

Constraints

• Each city has exactly one outgoing arc in the tour.

  \[ \sum_{j \in V,\, j \neq i} x_{ij} = 1 \quad \forall i \in V \]

• Each city has exactly one incoming arc in the tour.

  \[ \sum_{i \in V,\, i \neq j} x_{ij} = 1 \quad \forall j \in V \]

• MTZ subtour elimination constraint.

  \[ u_i - u_j + n \times x_{ij} \leq n - 1 \quad \forall i, j \in V \setminus \{0\},\; i \neq j \]

• Depot position is fixed to \(1\) to anchor the tour ordering.

  \[ u_0 = 1 \]

• Lower bound on MTZ position: each non-depot city’s position is at least \(2\).

  \[ u_i \geq 2 \quad \forall i \in V \setminus \{0\} \]

• Upper bound on MTZ position: each city’s position is at most \(n\).

  \[ u_i \leq n \quad \forall i \in V \]

• No self-loops: a city cannot have an arc to itself. (implicit)

  \[ x_{ii} = 0 \quad \forall i \in V \]

• Two-City Detour Elimination (EC3): eliminates infeasible two-city detours through the depot for any pair of non-depot cities \(i\), \(j\). This cut is invalid because it excludes the feasible \(1 \to 2 \to 3 \to 1\) tour when \(n=3\).

  \[ x_{j0} + x_{ji} + u_j - u_i - 1 \leq (n-1)(2 - x_{0i} - x_{ij}) \quad \forall i, j \in V \setminus \{0\},\; i \neq j \]

Objective

Minimize the total travel cost of the Hamiltonian cycle.

\[ \min \sum_{i \in V} \sum_{j \in V,\, j \neq i} c_{ij} \times x_{ij} \]

Formulation e (invalid)

See also

This formulation is sourced from EvoCut [2] (version: 2, name: EC1).

Note

• This is the MTZ formulation of the TSP from v2 of Yazdani et al. [2] augmented with acceleration cut EC1.

Parameters

Name	Description	Type	Shape
n	Number of cities	integer	scalar
c	Travel cost from city \(i\) to city \(j\)	continuous	[n, n]

Variables

Name	Description	Type	Shape / Indices
x	\(1\) if the tour goes directly from city \(i\) to city \(j\), \(0\) otherwise	binary	[n, n]
u	MTZ position of city \(i\) in the tour	continuous	[n]

Assumptions

Description	Formulation	Implicit
There must be at least two cities to form a tour.	\(n \geq 2\)	yes

Constraints

• Each city has exactly one outgoing arc in the tour.

  \[ \sum_{j \in V,\, j \neq i} x_{ij} = 1 \quad \forall i \in V \]

• Each city has exactly one incoming arc in the tour.

  \[ \sum_{i \in V,\, i \neq j} x_{ij} = 1 \quad \forall j \in V \]

• MTZ subtour elimination constraint.

  \[ u_i - u_j + n \times x_{ij} \leq n - 1 \quad \forall i, j \in V \setminus \{0\},\; i \neq j \]

• Depot position is fixed to \(1\) to anchor the tour ordering.

  \[ u_0 = 1 \]

• Lower bound on MTZ position: each non-depot city’s position is at least \(2\).

  \[ u_i \geq 2 \quad \forall i \in V \setminus \{0\} \]

• Upper bound on MTZ position: each city’s position is at most \(n\).

  \[ u_i \leq n \quad \forall i \in V \]

• No self-loops: a city cannot have an arc to itself. (implicit)

  \[ x_{ii} = 0 \quad \forall i \in V \]

• Arc Symmetry (EC1): both directions of an arc cannot be simultaneously active, eliminating two-city cycles. This cut is invalid because it excludes the feasible \(1 \to 2 \to 1\) tour when \(n=2\).

  \[ x_{ij} + x_{ji} \leq 1 \quad \forall i, j \in V,\; i < j \]

Objective

Minimize the total travel cost of the Hamiltonian cycle.

\[ \min \sum_{i \in V} \sum_{j \in V,\, j \neq i} c_{ij} \times x_{ij} \]

Formulation f (invalid)

See also

This formulation is sourced from EvoCut [2] (version: 2, name: EC2).

Note

• This is the MTZ formulation of the TSP from v2 of Yazdani et al. [2] augmented with acceleration cut EC2.

Parameters

Name	Description	Type	Shape
n	Number of cities	integer	scalar
c	Travel cost from city \(i\) to city \(j\)	continuous	[n, n]

Variables

Name	Description	Type	Shape / Indices
x	\(1\) if the tour goes directly from city \(i\) to city \(j\), \(0\) otherwise	binary	[n, n]
u	MTZ position of city \(i\) in the tour	continuous	[n]

Assumptions

Description	Formulation	Implicit
There must be at least two cities to form a tour.	\(n \geq 2\)	yes

Constraints

• Each city has exactly one outgoing arc in the tour.

  \[ \sum_{j \in V,\, j \neq i} x_{ij} = 1 \quad \forall i \in V \]

• Each city has exactly one incoming arc in the tour.

  \[ \sum_{i \in V,\, i \neq j} x_{ij} = 1 \quad \forall j \in V \]

• MTZ subtour elimination constraint.

  \[ u_i - u_j + n \times x_{ij} \leq n - 1 \quad \forall i, j \in V \setminus \{0\},\; i \neq j \]

• Depot position is fixed to \(1\) to anchor the tour ordering.

  \[ u_0 = 1 \]

• Lower bound on MTZ position: each non-depot city’s position is at least \(2\).

  \[ u_i \geq 2 \quad \forall i \in V \setminus \{0\} \]

• Upper bound on MTZ position: each city’s position is at most \(n\).

  \[ u_i \leq n \quad \forall i \in V \]

• No self-loops: a city cannot have an arc to itself. (implicit)

  \[ x_{ii} = 0 \quad \forall i \in V \]

• Depot Triangle (EC2): eliminates three-city subtours passing through the depot; at most 2 of the 6 arcs in any depot-adjacent triangle can be active. This cut is invalid because it excludes the feasible \(1 \to 2 \to 3 \to 1\) tour when \(n=3\).

  \[ x_{0i} + x_{i0} + x_{0j} + x_{j0} + x_{ij} + x_{ji} \leq 2 \quad \forall i, j \in V \setminus \{0\},\; i < j \]

Objective

Minimize the total travel cost of the Hamiltonian cycle.

\[ \min \sum_{i \in V} \sum_{j \in V,\, j \neq i} c_{ij} \times x_{ij} \]

Formulation g (valid)

See also

This formulation is sourced from EvoCut [2] (version: 2, name: EC3).

Note

• This is the MTZ formulation of the TSP from v2 of Yazdani et al. [2] augmented with acceleration cut EC3.

Parameters

Name	Description	Type	Shape
n	Number of cities	integer	scalar
c	Travel cost from city \(i\) to city \(j\)	continuous	[n, n]

Variables

Name	Description	Type	Shape / Indices
x	\(1\) if the tour goes directly from city \(i\) to city \(j\), \(0\) otherwise	binary	[n, n]
u	MTZ position of city \(i\) in the tour	continuous	[n]

Assumptions

Description	Formulation	Implicit
There must be at least two cities to form a tour.	\(n \geq 2\)	yes

Constraints

• Each city has exactly one outgoing arc in the tour.

  \[ \sum_{j \in V,\, j \neq i} x_{ij} = 1 \quad \forall i \in V \]

• Each city has exactly one incoming arc in the tour.

  \[ \sum_{i \in V,\, i \neq j} x_{ij} = 1 \quad \forall j \in V \]

• MTZ subtour elimination constraint.

  \[ u_i - u_j + n \times x_{ij} \leq n - 1 \quad \forall i, j \in V \setminus \{0\},\; i \neq j \]

• Depot position is fixed to \(1\) to anchor the tour ordering.

  \[ u_0 = 1 \]

• Lower bound on MTZ position: each non-depot city’s position is at least \(2\).

  \[ u_i \geq 2 \quad \forall i \in V \setminus \{0\} \]

• Upper bound on MTZ position: each city’s position is at most \(n\).

  \[ u_i \leq n \quad \forall i \in V \]

• No self-loops: a city cannot have an arc to itself. (implicit)

  \[ x_{ii} = 0 \quad \forall i \in V \]

• Lifted Desrochers-Laporte MTZ Ordering (EC3): strengthened MTZ constraint incorporating the reverse arc with a tighter coefficient.

  \[ u_i - u_j + (n-1) x_{ij} + (n-3) x_{ji} \leq n - 2 \quad \forall i, j \in V \setminus \{0\},\; i \neq j \]

Objective

Minimize the total travel cost of the Hamiltonian cycle.

\[ \min \sum_{i \in V} \sum_{j \in V,\, j \neq i} c_{ij} \times x_{ij} \]

Formulation h (valid)

See also

This formulation is sourced from EvoCut [2] (version: 2, name: EC4).

Note

• This is the MTZ formulation of the TSP from v2 of Yazdani et al. [2] augmented with acceleration cut EC4.

Parameters

Name	Description	Type	Shape
n	Number of cities	integer	scalar
c	Travel cost from city \(i\) to city \(j\)	continuous	[n, n]

Variables

Name	Description	Type	Shape / Indices
x	\(1\) if the tour goes directly from city \(i\) to city \(j\), \(0\) otherwise	binary	[n, n]
u	MTZ position of city \(i\) in the tour	continuous	[n]

Assumptions

Description	Formulation	Implicit
There must be at least two cities to form a tour.	\(n \geq 2\)	yes

Constraints

• Each city has exactly one outgoing arc in the tour.

  \[ \sum_{j \in V,\, j \neq i} x_{ij} = 1 \quad \forall i \in V \]

• Each city has exactly one incoming arc in the tour.

  \[ \sum_{i \in V,\, i \neq j} x_{ij} = 1 \quad \forall j \in V \]

• MTZ subtour elimination constraint.

  \[ u_i - u_j + n \times x_{ij} \leq n - 1 \quad \forall i, j \in V \setminus \{0\},\; i \neq j \]

• Depot position is fixed to \(1\) to anchor the tour ordering.

  \[ u_0 = 1 \]

• Lower bound on MTZ position: each non-depot city’s position is at least \(2\).

  \[ u_i \geq 2 \quad \forall i \in V \setminus \{0\} \]

• Upper bound on MTZ position: each city’s position is at most \(n\).

  \[ u_i \leq n \quad \forall i \in V \]

• No self-loops: a city cannot have an arc to itself. (implicit)

  \[ x_{ii} = 0 \quad \forall i \in V \]

• Lower MTZ Envelope (EC4): tightens the lower bound on city \(i\)’s position using its depot-adjacent arcs.

  \[ u_i \geq 3 - x_{0i} + (n-3) x_{i0} \quad \forall i \in V \setminus \{0\} \]

Objective

Minimize the total travel cost of the Hamiltonian cycle.

\[ \min \sum_{i \in V} \sum_{j \in V,\, j \neq i} c_{ij} \times x_{ij} \]

Formulation i (valid)

See also

This formulation is sourced from EvoCut [2] (version: 2, name: EC5).

Note

• This is the MTZ formulation of the TSP from v2 of Yazdani et al. [2] augmented with acceleration cut EC5.

Parameters

Name	Description	Type	Shape
n	Number of cities	integer	scalar
c	Travel cost from city \(i\) to city \(j\)	continuous	[n, n]

Variables

Name	Description	Type	Shape / Indices
x	\(1\) if the tour goes directly from city \(i\) to city \(j\), \(0\) otherwise	binary	[n, n]
u	MTZ position of city \(i\) in the tour	continuous	[n]

Assumptions

Description	Formulation	Implicit
There must be at least two cities to form a tour.	\(n \geq 2\)	yes

Constraints

• Each city has exactly one outgoing arc in the tour.

  \[ \sum_{j \in V,\, j \neq i} x_{ij} = 1 \quad \forall i \in V \]

• Each city has exactly one incoming arc in the tour.

  \[ \sum_{i \in V,\, i \neq j} x_{ij} = 1 \quad \forall j \in V \]

• MTZ subtour elimination constraint.

  \[ u_i - u_j + n \times x_{ij} \leq n - 1 \quad \forall i, j \in V \setminus \{0\},\; i \neq j \]

• Depot position is fixed to \(1\) to anchor the tour ordering.

  \[ u_0 = 1 \]

• Lower bound on MTZ position: each non-depot city’s position is at least \(2\).

  \[ u_i \geq 2 \quad \forall i \in V \setminus \{0\} \]

• Upper bound on MTZ position: each city’s position is at most \(n\).

  \[ u_i \leq n \quad \forall i \in V \]

• No self-loops: a city cannot have an arc to itself. (implicit)

  \[ x_{ii} = 0 \quad \forall i \in V \]

• Upper MTZ Envelope (EC5): tightens the upper bound on city \(i\)’s position using its depot-adjacent arcs.

  \[ u_i \leq (n-1) + x_{i0} - (n-3) x_{0i} \quad \forall i \in V \setminus \{0\} \]

Objective

Minimize the total travel cost of the Hamiltonian cycle.

\[ \min \sum_{i \in V} \sum_{j \in V,\, j \neq i} c_{ij} \times x_{ij} \]

Reformulations

Each entry below pairs two formulations of this problem, records whether the second is a reformulation of the first, and gives the parameter map carrying the first formulation’s parameters to the second’s.

a → b (valid)

Note

• Formulation b has the same parameters as formulation a; the map is the identity.

Parameter map

Name	Definition in terms of a
n	\(n = n\)
c	\(c_{ij} = c_{ij}\)

a → c (valid)

Note

• Formulation c has the same parameters as formulation a; the map is the identity.

Parameter map

Name	Definition in terms of a
n	\(n = n\)
c	\(c_{ij} = c_{ij}\)

a → d (invalid)

Note

• Formulation d has the same parameters as formulation a; the map is the identity.

Parameter map

Name	Definition in terms of a
n	\(n = n\)
c	\(c_{ij} = c_{ij}\)

a → e (invalid)

Note

• Formulation e has the same parameters as formulation a; the map is the identity.

Parameter map

Name	Definition in terms of a
n	\(n = n\)
c	\(c_{ij} = c_{ij}\)

a → f (invalid)

Note

• Formulation f has the same parameters as formulation a; the map is the identity.

Parameter map

Name	Definition in terms of a
n	\(n = n\)
c	\(c_{ij} = c_{ij}\)

a → g (valid)

Note

• Formulation g has the same parameters as formulation a; the map is the identity.

Parameter map

Name	Definition in terms of a
n	\(n = n\)
c	\(c_{ij} = c_{ij}\)

a → h (valid)

Note

• Formulation h has the same parameters as formulation a; the map is the identity.

Parameter map

Name	Definition in terms of a
n	\(n = n\)
c	\(c_{ij} = c_{ij}\)

a → i (valid)

Note

• Formulation i has the same parameters as formulation a; the map is the identity.

Parameter map

Name	Definition in terms of a
n	\(n = n\)
c	\(c_{ij} = c_{ij}\)