p12 | Traveling Salesman Problem (TSP)

See also

This problem is sourced from EvoCut.

Note

• EvoCut arXiv submission v1 proposes three inequalities used to generate formulations p12.b-d.

• EvoCut arXiv submission v2 proposes five inequalities used to generate formulations p12.e-i.

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.

Note

• This is the Miller-Tucker-Zemlin (MTZ) MILP formulation given in Section F.1 of EvoCut arXiv submission v1.

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 \cdot 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 non-depot city’s position is at most n.

  \[ u_i \leq n \quad \forall i \in V \setminus \{0\} \]

• 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} \cdot x_{ij} \]

Formulation b (valid)

See also

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

Note

• If the tour leaves the depot directly to city \(j\), then \(j\)’s MTZ position \(u_j\) must be at most \(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 \cdot 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 non-depot city’s position is at most n.

  \[ u_i \leq n \quad \forall i \in V \setminus \{0\} \]

• 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} \cdot x_{ij} \]

Formulation c (valid)

See also

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

Note

• If the tour returns to the depot from city \(i\), then \(i\)’s MTZ position \(u_i\) must be exactly \(n\) (last).

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 \cdot 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 non-depot city’s position is at most n.

  \[ u_i \leq n \quad \forall i \in V \setminus \{0\} \]

• 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} \cdot x_{ij} \]

Formulation d (invalid)

See also

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

Note

• Eliminate triangles involving the depot.

• This cut was identified by FLARE to be invalid. The inequality prevents the feasible \(1 \to 2 \to 3 \to 1\) tour for \(n=3\) TSP instances.

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 \cdot 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 non-depot city’s position is at most n.

  \[ u_i \leq n \quad \forall i \in V \setminus \{0\} \]

• 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.

  \[ 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} \cdot x_{ij} \]

Formulation e (invalid)

See also

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

Note

• Eliminate two-city tours.

• This cut was identified by FLARE to be invalid. The inequality prevents the feasible \(1 \to 2 \to 1\) tour for \(n=2\) TSP instances.

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 \cdot 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 non-depot city’s position is at most n.

  \[ u_i \leq n \quad \forall i \in V \setminus \{0\} \]

• 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.

  \[ 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} \cdot x_{ij} \]

Formulation f (invalid)

See also

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

Note

• Eliminate triangles involving the depot.

• This cut was identified by FLARE to be invalid. The inequality prevents the feasible \(1 \to 2 \to 3 \to 1\) tour for \(n=3\) TSP instances.

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 \cdot 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 non-depot city’s position is at most n.

  \[ u_i \leq n \quad \forall i \in V \setminus \{0\} \]

• 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.

  \[ 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} \cdot x_{ij} \]

Formulation g (valid)

See also

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

Note

• Strengthened MTZ ordering (Desrochers-Laporte lifting): incorporates the reverse arc \(x_{ji}\) with coefficient \(n-3\), tightening the standard MTZ subtour-elimination inequality.

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 \cdot 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 non-depot city’s position is at most n.

  \[ u_i \leq n \quad \forall i \in V \setminus \{0\} \]

• 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} \cdot x_{ij} \]

Formulation h (valid)

See also

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

Note

• City \(i\)’s MTZ position is at least \(3 - x_{0i} + (n-3) x_{i0}\), tightening the lower bound using its depot-adjacent arcs.

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 \cdot 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 non-depot city’s position is at most n.

  \[ u_i \leq n \quad \forall i \in V \setminus \{0\} \]

• 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} \cdot x_{ij} \]

Formulation i (valid)

See also

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

Note

• City \(i\)’s MTZ position is at most \((n-1) + x_{i0} - (n-3) x_{0i}\), tightening the upper bound using its depot-adjacent arcs.

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 \cdot 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 non-depot city’s position is at most n.

  \[ u_i \leq n \quad \forall i \in V \setminus \{0\} \]

• 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} \cdot x_{ij} \]