<jupyter_start><jupyter_text>Traveling Salesman Problem Objective and PrerequisitesIn this example, you’ll learn how to tackle one of the most famous combinatorial optimization problems in existence: the Traveling Salesman Problem (TSP). The goal of the TSP – to find the shortest possible route that visits each city once and returns to the original city – is simple, but solving the problem is a complex and challenging endeavor. We’ll show you how to do it!This modeling example is at the advanced level, where we assume that you know Python and the Gurobi Python API and that you have advanced knowledge of building mathematical optimization models. Typically, the objective function and/or constraints of these examples are complex or require advanced features of the Gurobi Python API.**Download the Repository** You can download the repository containing this and other examples by clicking [here](https://github.com/Gurobi/modeling-examples/archive/master.zip). **Gurobi License** In order to run this Jupyter Notebook properly, you must have a Gurobi license. If you do not have one, you can request an [evaluation license](https://www.gurobi.com/downloads/request-an-evaluation-license/?utm_source=3PW&utm_medium=OT&utm_campaign=WW-MU-RAO-OR-O_LEA-PR_NO-Q3_FY20_WW_JPME_traveling-salesman_COM_EVAL_GITHUB_&utm_term=traveling-salesman-problem&utm_content=C_JPM) as a *commercial user*, or download a [free license](https://www.gurobi.com/academia/academic-program-and-licenses/?utm_source=3PW&utm_medium=OT&utm_campaign=WW-MU-RAO-OR-O_LEA-PR_NO-Q3_FY20_WW_JPME_traveling-salesman_ACADEMIC_EVAL_GITHUB_&utm_term=traveling-salesman-problem&utm_content=C_JPM) as an *academic user*.  MotivationThe Traveling Salesman Problem (TSP) is one of the most famous combinatorial optimization problems. This problem is very easy to explain, but very complicated to solve – even for instances with a small number of cities. More detailed information on the TSP can be found in the book The Traveling Salesman Problem: A Computational Study [1], or at the TSP home page [2]. If you are interested in the history and mathematical background of the TSP, we recommend that you watch the video by <NAME> [3].The origin of the traveling salesman problem is not very clear; it is mentioned in an 1832 manual for traveling salesman, which included example tours of 45 German cities but was not formulated as a mathematical problem. However, in the 1800s, mathematicians <NAME> and <NAME> devised mathematical formulations of the problem.It seems that the general form of the Traveling Salesman Problem was first studied by <NAME> in Vienna and Harvard in the 1930s.The problem became more and more popular in the 1950s and 1960s. In particular, <NAME>, <NAME>, and <NAME> at the RAND Corporation solved the 48-state problem by formulating it as a linear programming problem. The methods they described in their paper on this topic set the foundation for future work in combinatorial optimization, especially highlighting the importance of cutting planes.In the early 1970s, the concept of P vs. NP problems created excitement in the theoretical computer science community. In 1972, <NAME> demonstrated that the Hamiltonian cycle problem was NP-complete, implying that the traveling salesman problem was NP-hard.Increasingly sophisticated codes led to rapid increases in the sizes of the traveling salesman problems solved. Dantzig, Fulkerson, and Johnson had solved a 48-city instance of the problem in 1954. <NAME> more than doubled this 23 years later, solving a 120-city instance in 1977. <NAME> and <NAME> again more than doubled this in just 3 years, with a 318-city solution.In 1987, rapid improvements were made, culminating in a 2,392-city solution by Padberg and <NAME>. In the following two decades, great strides were made with <NAME>, <NAME>, <NAME>, & <NAME> solving a 3,308-city instance in 1992, a 7,397-city instance in 1994, a 24,978-city instance in 2004, and an 85,900-city instance in 2006 – which is the largest 2-D Euclidean TSP instance ever solved. William Cook et. al. wrote a program called Concorde TSP Solver for solving the TSP [4]. Concorde is a computer code for the symmetric TSP and some related network optimization problems. The code is written in the ANSI C programming language and it has been used to obtain the optimal solutions to the full set of 110 TSPLIB instances, the largest instance is a 109,399 node 3-D “star” instance.The continued interest in the TSP can be explained by its success as a general engine of discovery and a steady stream of new applications. Some of the general applications of the TSP are as follows:* Scheduling and routing problems.* Genome sequencing.* Drilling problems.* Aiming telescopes and x-rays.* Data clustering.* Machine scheduling.We use this classic combinatorial optimization problem to demonstrate how Gurobi can be used to easily and effectively solve small-sized problem instances of the TSP. However, in order to be able to solve larger instances, one needs more sophisticated techniques – such as those implemented in the Concord TSP Solver.  Problem DescriptionThe TSP can be defined as follows: for a given list of cities and the distances between each pair of them, we want to find the shortest possible route that goes to each city once and returns to the origin city.There is a class of Traveling Salesman Problems that assumes that the distance of going from city $i$ to city $j$  is the same as going form city $j$ to city $i$, this type of Traveling Salesman Problem  is also known as the symmetric Traveling Salesman Problem. In this example, we use Euclidean distances, but the TSP model formulation is valid independent of the way in which the individual distances are determined. Solution ApproachMathematical programming is a declarative approach where the modeler formulates a mathematical optimization model that captures the key aspects of a complex decision problem. The Gurobi Optimizer solves such models using state-of-the-art mathematics and computer science.A mathematical optimization model has five components, namely:* Sets and indices.* Parameters.* Decision variables.* Objective function(s).* Constraints.We now present a MIP formulation of the TSP that identifies the shortest route that goes to all the cities once and returns to the origin city. TSP Model Formulation Sets and Indices$i, j \in Capitals $: indices and set of US capital cities.$\text{Pairings}= \{(i,j) \in Capitals \times Capitals \}$: Set of allowed pairings$S \subset Capitals$: A subset of the set of US capital cities.$G = (Capitals, Pairings)$: A graph where the set $Capitals$ defines the set of nodes and the set $Pairings$ defines the set of edges.  Parameters $d_{i, j} \in \mathbb{R}^+$: Distance from capital city $i$ to capital city $j$, for all $(i, j) \in Pairings$. Notice that the distance from capital city $i$ to capital city $j$ is the same as the distance from capital city $j$ to capital city $i$, i.e. $d_{i, j} = d_{j, i}$. For this reason, this TSP is also called the symmetric Traveling Salesman Problem. Decision Variables$x_{i, j} \in \{0, 1\}$: This variable is equal to 1, if we decide to connect city $i$ with city $j$. Otherwise, the decision variable is equal to zero. Objective Function- **Shortest Route**. Minimize the total distance of a route. A route is a sequence of capital cities where the salesperson visits each city only once and returns to the starting capital city.\begin{equation}\text{Min} \quad Z = \sum_{(i,j) \in \text{Pairings}}d_{i,j} \cdot x_{i,j}\tag{0}\end{equation} Constraints - **Symmetry Constraints**. For each edge $(i,j)$, ensure that the city capitals $i$ and $j$ are connected, if the former is visited immediately before or after visiting the latter.\begin{equation}x_{i, j} = x_{j, i} \quad \forall (i, j) \in Pairings\tag{1}\end{equation}- **Entering and leaving a capital city**. For each capital city $i$, ensure that this city is connected to two other cities. \begin{equation}\sum_{(i,j) \in \text{Pairings}}x_{i,j} = 2 \quad \forall  i \in Capitals\tag{2}\end{equation}- **Subtour elimination**. These constraints ensure that for any subset of cities $S$ of the set of $Capitals$, there is no cycle. That is, there is no route that visits all the cities in the subset and returns to the origin city.\begin{equation}\sum_{(i \neq j) \in S}x_{i,j} \leq |S|-1 \quad \forall  S \subset  Capitals\tag{3}\end{equation}- **Remark**. In general, if the number of cities of the TSP is $n$, then the possible number of routes is n\!.Since there are an exponential number of constraints ($2^{n} - 2$) to eliminate cycles, we use lazy constraints to dynamically eliminate those cycles.   Python ImplementationConsider a salesperson that needs to visit customers at each state capital of the continental US. The salesperson wants to identify the shortest route that goes to all the state capitals.This modeling example requires the following libraries that are not part of the standard Python distribution:* **folium**: to create maps.* **gurobipy**: provides Gurobi algorithms to solve MIP models.  Reading Input DataThe capital names and coordinates are read from a json file.<jupyter_code>import json

# Read capital names and coordinates from json file
capitals_json = json.load(open('capitals.json'))
capitals = []
coordinates = {}
for state in capitals_json:
    if state not in ['AK', 'HI']:
      capital = capitals_json[state]['capital']
      capitals.append(capital)
      coordinates[capital] = (float(capitals_json[state]['lat']), float(capitals_json[state]['long']))<jupyter_output><empty_output><jupyter_text>Data computationThe following function calculates the distance for each pair of state capitals. Since we are solving the _symmetric_ traveling salesman problem, we use _combinations_ of cities.<jupyter_code>import math
from itertools import combinations

# Compute pairwise distance matrix

def distance(city1, city2):
    c1 = coordinates[city1]
    c2 = coordinates[city2]
    diff = (c1[0]-c2[0], c1[1]-c2[1])
    return math.sqrt(diff[0]*diff[0]+diff[1]*diff[1])

dist = {(c1, c2): distance(c1, c2) for c1, c2 in combinations(capitals, 2)}<jupyter_output><empty_output><jupyter_text>Model CodeWe now write the model for the TSP, by defining decision variables, constraints, and objective function. Because this is the _symmetric_ traveling salesman problem, we can make it more efficient by setting the _object_ x[j,i] to x[i,j], instead of a constraint.<jupyter_code>import gurobipy as gp
from gurobipy import GRB

# tested with Python 3.7 & Gurobi 9.0.0

m = gp.Model()

# Variables: is city 'i' adjacent to city 'j' on the tour?
vars = m.addVars(dist.keys(), obj=dist, vtype=GRB.BINARY, name='x')

# Symmetric direction: Copy the object
for i, j in vars.keys():
    vars[j, i] = vars[i, j]  # edge in opposite direction

# Constraints: two edges incident to each city
cons = m.addConstrs(vars.sum(c, '*') == 2 for c in capitals)<jupyter_output><empty_output><jupyter_text>Callback DefinitionSubtour constraints prevent multiple loops in a TSP tour. Because there are an exponential number of these constraints, we don't want to add them all to the model. Instead, we use a callback function to find violated subtour constraints and add them to the model as lazy constraints.<jupyter_code># Callback - use lazy constraints to eliminate sub-tours

def subtourelim(model, where):
    if where == GRB.Callback.MIPSOL:
        # make a list of edges selected in the solution
        vals = model.cbGetSolution(model._vars)
        selected = gp.tuplelist((i, j) for i, j in model._vars.keys()
                             if vals[i, j] > 0.5)
        # find the shortest cycle in the selected edge list
        tour = subtour(selected)
        if len(tour) < len(capitals):
            # add subtour elimination constr. for every pair of cities in subtour
            model.cbLazy(gp.quicksum(model._vars[i, j] for i, j in combinations(tour, 2))
                         <= len(tour)-1)

# Given a tuplelist of edges, find the shortest subtour

def subtour(edges):
    unvisited = capitals[:]
    cycle = capitals[:] # Dummy - guaranteed to be replaced
    while unvisited:  # true if list is non-empty
        thiscycle = []
        neighbors = unvisited
        while neighbors:
            current = neighbors[0]
            thiscycle.append(current)
            unvisited.remove(current)
            neighbors = [j for i, j in edges.select(current, '*')
                         if j in unvisited]
        if len(thiscycle) <= len(cycle):
            cycle = thiscycle # New shortest subtour
    return cycle<jupyter_output><empty_output><jupyter_text>Solve the model<jupyter_code>m._vars = vars
m.Params.lazyConstraints = 1
m.optimize(subtourelim)<jupyter_output><empty_output><jupyter_text>AnalysisWe retrieve the optimal solution of the TSP and verify that the optimal route (or tour) goes to all the cities and returns to the origin city.<jupyter_code># Retrieve solution

vals = m.getAttr('x', vars)
selected = gp.tuplelist((i, j) for i, j in vals.keys() if vals[i, j] > 0.5)

tour = subtour(selected)
assert len(tour) == len(capitals)<jupyter_output><empty_output><jupyter_text>The optimal route is displayed in the following map.<jupyter_code># Map the solution

import folium

map = folium.Map(location=[40,-95], zoom_start = 4)

points = []
for city in tour:
  points.append(coordinates[city])
points.append(points[0])

folium.PolyLine(points).add_to(map)

map<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.07683232561569091, 'fraction_numerical': 0.012682495207196578, 'mean_word_length': 4.524643584521385, 'pattern_counts': {'":': 0, '<': 48, '<?xml version=': 0, '>': 47, 'https://': 3, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '80933', 'license': 'Apache-2.0', 'n_tokens_mistral': 3880, 'n_tokens_neox': 3618, 'n_words': 1785, 'path': 'traveling_salesman/tsp.ipynb', 'repo_name': 'pobonomo/modeling-examples', 'size': '13709'}