Travelling Salesman Problem (I)

23 Mar 2026 in Optimisation Last modified at: 2026-04-05

An intuitive introduction to the Travelling Salesman Problem, its mathematical formulation, and the role of subtour elimination constraints.

Disclaimer
The opinions expressed in this article are solely my own and do not reflect the views of any company or organisation I may be affiliated with.

Cover image source: Applying the Traveling Salesman Problem to Business – Russ Penlington

No generative AI was used in the writing of this article. Enjoy the read :)

Why the Travelling Salesman Problem?

Well, as you might already have noticed, I’m really keen on operations research and optimisation. As such, I’m pretty sure there is no better first blog post than one that dives into the (probably) most well-known problem in optimisation: the Travelling Salesman Problem (TSP). I’m actually a big fan of this specific problem, as I love the dichotomy between complexity and simplicity. TSP is simple in the sense that it is a very intuitive problem: everybody can understand it since it is very practical and rooted in real-world situations. At the same time, it is complex, as solving it optimally has been an area of research on its own for decades.

A bit of history

I’m not the biggest fan of assigning a specific date or an “inventor” to a given problem, as these usually come after years of incremental research. Especially for such a practical problem like the TSP, I’m pretty sure humans were trying to solve it long before it had a name. That said, the problem was formulated mathematically in the 1940s by Merrill M. Flood (USA), although it had already been studied earlier by Karl Menger in Vienna (at the time Austria-Hungary). This formalisation is what allowed the problem to become a cornerstone of optimisation research.

A real-world interpretation

Imagine yourself as a courier at a delivery company. Your shift leader assigns you 10 orders that you need to deliver to 10 different locations in the afternoon. As a measure of efficiency, you are told that you are free the moment all deliveries are completed.

Naturally, since you want to get off work as soon as possible, you are faced with a very interesting optimisation problem: what is the optimal route (i.e., in which order should I deliver the 10 orders) such that the total travel time is minimised? In this story, the objective is time, but it could just as well be total cost, fuel consumption, or any other metric (time and cost are usually intrinsically correlated).

Here comes the bad news: this problem sounds much easier than it actually is. In theory, you could brute-force every possible route and compare their total travel times. In practice, however, this quickly becomes infeasible.

For just 10 locations, you would need to check $10! = 10 \times 9 \times 8 \times \dots \times 2 \times 1 = 3{,}628{,}800$ possible routes. And by the time you have evaluated all of them, I believe your shift would already be over.

This is precisely why the TSP is such a famous problem: its complexity grows extremely fast as the number of cities increases.

NP-hardness

In fact, this explosion in the number of possible routes is closely related to a well-known concept in optimisation and computer science: NP-hardness.

The Travelling Salesman Problem belongs to a class of problems that are considered computationally very difficult to solve exactly. More precisely, the optimisation version of the TSP is NP-hard, which means that no algorithm is known that can solve every instance efficiently as the number of cities grows.

In practical terms, this means that although finding the best route is theoretically possible, doing so exactly can become computationally prohibitive even for moderately sized instances. As the problem grows, the time required to guarantee optimality may increase dramatically.

This theoretical difficulty has an important practical consequence: in many applications, exact optimality is simply not the main priority.

Optimal vs. practical solutions

In most applications, companies are not actually interested in the best (that is optimal) solution. Theoretically they would be, but in practice computing it often takes too long to be useful. Instead, a “good enough” solution is usually more than sufficient.

These solutions are typically found using heuristic methods, which aim to produce high-quality solutions in a reasonable amount of time.

In this blog post, I will focus on the mathematical formulation of the TSP. In the next post (this blog post will be divided into two), I will go over some of the most common heuristics used to tackle it.

The mathematical model

Let’s first introduce the decision variable:

$$x_{ij} = \begin{cases} 1, & \text{if city } j \text{ is visited immediately after city } i \\ 0, & \text{otherwise} \end{cases}$$

Using this decision variable, the Travelling Salesman Problem can be formulated as the following optimisation model:

$$\begin{aligned} \min \quad & \sum_{i=1}^{n}\sum_{j=1}^{n} c_{ij}\,x_{ij} \\[4pt] \text{s.t.}\quad & \sum_{i=1}^{n} x_{ij} = 1 && \forall\, j\in\{1,\ldots,n\} \\ & \sum_{j=1}^{n} x_{ij} = 1 && \forall\, i\in\{1,\ldots,n\} \\ & x_{ij}\in\{0,1\},\qquad 1\le i\le n,\; 1\le j\le n \end{aligned}$$

The objective function minimises the total travel cost, where $c_{ij}$ represents the cost (e.g. time or distance) of traveling directly from city $i$ to city $j$.

The first constraint ensures that each city is visited exactly once. In other words, for every city $j$, there must be exactly one city $i$ from which the salesman arrives.

The second constraint ensures that each city is departed from exactly once. That is, for every city $i$, the salesman must leave it and go to exactly one other city $j$.

Finally, the binary constraint on $x_{ij}$ enforces the combinatorial nature of the problem, ensuring that routes are either chosen or not chosen. Together, these constraints define a valid tour that visits every city exactly once while minimising the total cost.

Why this is not enough

For those reading the article a bit more carefully, you may already have noticed that the formulation presented above is still incomplete. Why? Because, as it stands, it does not guarantee that we obtain one single tour visiting all cities.

To see this more clearly, let us consider a simpler case with only 4 cities instead of 10. Suppose the following solution is proposed:

$$x_{12}=x_{21}=x_{34}=x_{43}=1$$

and all other decision variables are equal to zero.

Graphically, this would look something like this:

Example of a feasible solution that satisfies the degree constraints but results in two disconnected subtours.

Now, let us check whether this solution satisfies all the constraints of the model.

Incoming constraints

Each city must have exactly one incoming connection.

For city 1: $x_{11} + x_{21} + x_{31} + x_{41} = 1$

Since in our solution only $x_{21}=1$, this becomes:

$$0 + 1 + 0 + 0 = 1 \qquad \checkmark$$

For city 2: $x_{12} + x_{22} + x_{32} + x_{42} = 1$

Since only $x_{12}=1$, we get:

$$1 + 0 + 0 + 0 = 1 \qquad \checkmark$$

For city 3: $x_{13} + x_{23} + x_{33} + x_{43} = 1$

Since only $x_{43}=1$, we get:

$$0 + 0 + 0 + 1 = 1 \qquad \checkmark$$

For city 4: $x_{14} + x_{24} + x_{34} + x_{44} = 1$

Since only $x_{34}=1$, we get:

$$0 + 0 + 1 + 0 = 1 \qquad \checkmark$$

Outgoing constraints

Each city must also have exactly one outgoing connection.

For city 1: $x_{11} + x_{12} + x_{13} + x_{14} = 1$

Since only $x_{12}=1$, this becomes:

$$0 + 1 + 0 + 0 = 1 \qquad \checkmark$$

For city 2: $x_{21} + x_{22} + x_{23} + x_{24} = 1$

Since only $x_{21}=1$, we get:

$$1 + 0 + 0 + 0 = 1 \qquad \checkmark$$

For city 3: $x_{31} + x_{32} + x_{33} + x_{34} = 1$

Since only $x_{34}=1$, we get:

$$0 + 0 + 0 + 1 = 1 \qquad \checkmark$$

For city 4: $x_{41} + x_{42} + x_{43} + x_{44} = 1$

Since only $x_{43}=1$, we get:

$$0 + 0 + 1 + 0 = 1 \qquad \checkmark$$

Binary constraints

Finally, all decision variables must be binary:

$$x_{ij}\in\{0,1\}\qquad \forall i,j$$

This is also satisfied, since every variable in the proposed solution is either 0 or 1. So, surprisingly, this solution satisfies all the constraints introduced so far. And yet, it is clearly not a valid solution to the Travelling Salesman Problem.

The reason is simple: instead of having one complete tour passing through all four cities, we end up with two disconnected loops:

• one loop between cities 1 and 2,
• another loop between cities 3 and 4.

These disconnected loops are called subtours. This is exactly the issue with the formulation presented so far: it ensures that every city is entered once and left once, but it does not ensure that all cities belong to the same tour.

So, if we want to model the TSP correctly, we still need to add extra constraints that eliminate subtours.

Subtour elimination

Formulation 1

Let $V$ be the set of all cities (or destinations) to be visited, and let $S$ be any non-empty subset of $V$, with $S \neq V$. In other words, $S$ is any proper subset of the full set of cities.

The key idea is the following: if a subset of cities $S$ forms a closed loop on its own, then a subtour appears. So, in order to prevent this, we must ensure that the number of arcs connecting cities within the subset $S$ is strictly limited.

Mathematically, this is written as:

$$\sum_{i\in S}\sum_{j\in S} x_{ij} \le |S|-1 \qquad \forall S \subset V,\; S\neq \emptyset,\; S\neq V$$

This means that, for any subset $S$, the number of selected arcs that start and end inside $S$ must be at most $\lvert S \rvert - 1$.

Why does this work? Because if $S$ contains $\lvert S \rvert$ cities, then a closed cycle involving only the cities of $S$ would require exactly $\lvert S \rvert$ internal arcs. By imposing the constraint above, we forbid that from happening. In other words, the cities in $S$ cannot form an independent loop disconnected from the rest of the tour.

Why this becomes computationally expensive

The fact that this formulation fixes the subtour problem does not mean that it comes for free. In optimisation, every time we add constraints to a MILP model, the problem generally becomes harder to solve.

In this case, the issue is that the subtour elimination constraint must be written for every non-empty proper subset $S$ of $V$. Now let us think about how many such subsets exist. Suppose the set $V$ has $n$ cities. For each city, there are two possibilities:

• either it belongs to the subset $S$,
• or it does not.

This means that the total number of possible subsets of $V$ is $2^n$. However, two of these subsets are not allowed in the subtour elimination constraint:

• the empty set $\emptyset$,
• the full set $V$ itself.

So the total number of relevant subsets is $2^n - 2$.

This also means that the number of subtour elimination constraints grows exponentially with the number of cities. For example, if we have only $n=10$ cities, then the number of such constraints is: $2^{10}-2 = 1024-2 = 1022$.

That is already a very large number, especially when compared to the original formulation, which only had a relatively small set of degree constraints. So, although this formulation is mathematically correct and elegant, it quickly becomes computationally intensive as the size of the problem grows. This is why, in practice, researchers and industry often look for alternative formulations or more efficient ways of generating these constraints.

Formulation 2

Another possible way of eliminating subtours is to formulate the condition from a slightly different perspective.

Instead of limiting the number of arcs that remain entirely inside a subset of cities, we can require that every non-empty proper subset of cities must have at least one selected arc leaving it.

Mathematically, this can be written as:

$$\sum_{i\in S}\sum_{j\in \bar{S}} x_{ij} \ge 1 \qquad \forall S \subset V,\; S\neq \emptyset,\; \bar{S}\neq \emptyset$$

Here, $\bar{S}$ denotes the complement of $S$, that is, the set of cities that do not belong to $S$.

The interpretation is quite intuitive. Take any subset of cities $S$. If that subset were to form a disconnected subtour, then no selected arc would leave it and connect it to the remaining cities. This constraint prevents that from happening by forcing at least one arc to go from a city in $S$ to a city outside $S$.

So, just like Formulation 1, this family of constraints also eliminates subtours. The main difference is simply the way the condition is expressed: Formulation 1 limits the number of arcs that stay inside the subset, whereas Formulation 2 requires at least one arc to leave it.

However, this does not improve the computational issue discussed before, since this constraint must still be written for every non-empty proper subset of $V$. Therefore, the total number of such constraints is again $2^n - 2$, so this formulation is not really better than Formulation 1 from that point of view.

Formulation 3

A third and very well-known way of eliminating subtours is to introduce auxiliary variables and use them to impose an ordering on the cities visited in the tour. This is the idea behind the Miller-Tucker-Zemlin (MTZ) formulation.

The additional constraints are written as:

$$u_i - u_j + n x_{ij} \le n - 1 \qquad 2 \le i,j \le n$$

where $u_i$ and $u_j$ are auxiliary variables associated with the cities.

The intuition behind this formulation is quite different from the previous two. Formulations 1 and 2 try to eliminate subtours by explicitly looking at subsets of cities. Here, instead, the variables $u_i$ are used to encode the relative position of each city in the route. In that sense, they help impose a logical ordering on the tour.

Why does this help? Suppose that arc $\left(i,j\right)$ is selected, so that $x_{ij}=1$. Then the constraint becomes:

$$u_i - u_j + n \le n - 1$$

which is equivalent to:

$$u_i - u_j \le -1 \qquad \Longleftrightarrow \qquad u_i < u_j$$

So, whenever the tour goes directly from city $i$ to city $j$, the corresponding auxiliary variables must respect that order.

On the other hand, if arc $\left(i,j\right)$ is not selected, so that $x_{ij}=0$, then the constraint becomes:

$$u_i - u_j \le n - 1$$

which is not restrictive in practice. So the ordering effect only becomes active on the arcs that are actually selected in the solution.

This is what blocks subtours. If a cycle were formed among a subset of cities that does not include the reference city, the MTZ constraints would force a chain of strict inequalities of the form:

$$u_{i_1} < u_{i_2} < u_{i_3} < \dots < u_{i_k} < u_{i_1}$$

which is impossible. Therefore, such subtours cannot exist.

So, just like the previous formulations, this one also eliminates subtours. The main difference is that it does so indirectly, through ordering variables, rather than through constraints written over subsets of cities.

An important advantage of this formulation is that it requires far fewer constraints. While Formulations 1 and 2 require one constraint for every non-empty proper subset of $V$, this formulation adds only $\left(n-1\right)^2$ constraints.

This is a significant reduction. For example, with $n=10$ cities:

• Formulations 1 and 2 require $2^{10}-2 = 1022$ subtour elimination constraints,
• whereas Formulation 3 requires only $\left(10-1\right)^2 = 81$ such constraints.

That sounds much better, and from a modelling point of view it often is. However, this does not automatically mean that Formulation 3 is always computationally superior in practice. The reason is that we now need to introduce the auxiliary variables $u_i$, and formulations based on such variables can sometimes lead to weaker linear relaxations or less favorable numerical behaviour for the solver.

Full MTZ formulation

For consistency, the full Travelling Salesman Problem with MTZ subtour elimination constraints can be written as:

$$\begin{aligned} \min \quad & \sum_{i=1}^{n}\sum_{j=1}^{n} c_{ij}\,x_{ij} \\[4pt] \text{s.t.}\quad & \sum_{i=1}^{n} x_{ij} = 1 && \forall\, j\in\{1,\ldots,n\} \\[4pt] & \sum_{j=1}^{n} x_{ij} = 1 && \forall\, i\in\{1,\ldots,n\} \\[4pt] & u_i - u_j + n x_{ij} \le n - 1 && \forall\, i,j\in\{2,\ldots,n\},\; i\neq j \\[4pt] & x_{ij}\in\{0,1\} && \forall\, i,j\in\{1,\ldots,n\} \\[4pt] & u_i \in \mathbb{R} && \forall\, i\in\{2,\ldots,n\} \end{aligned}$$

Final thoughts

The Travelling Salesman Problem is one of the most famous problems in optimisation for a very good reason. On the one hand, it is easy to understand and can be explained through very intuitive examples. On the other hand, once we try to solve it optimally, its complexity grows extremely fast and quickly becomes challenging from a computational point of view.

In this post, I introduced the basic idea behind the TSP, explained why it is considered such an important problem, and presented its mathematical formulation. I also showed why the basic degree constraints are not enough, since they allow subtours, and then discussed three different ways of eliminating them.

In the next part of this post, I will move away from exact formulations and focus on more practical solution approaches. In particular, I will go over some of the most common heuristic methods used to tackle the TSP, and I will also include some code to illustrate how these ideas can be implemented in practice. Stay tuned :)