---
tocdepth: 3
---

# p12 | Traveling Salesman Problem (TSP)

```{seealso}
This problem is sourced from [EvoCut](https://arxiv.org/abs/2508.11850).
```

```{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)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850).
```

```{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)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850) (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)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850) (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)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850) (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)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850) (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)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850) (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)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850) (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)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850) (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)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850) (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} $$