<jupyter_start><jupyter_text>Traveling Salesman Problem
Adapted from: [PYTHON-MIP Examples](https://python-mip.readthedocs.io/en/latest/examples.html)<jupyter_code>import numpy as np
from scipy.spatial import distance_matrix
import cvxpy as cvx
import matplotlib.pyplot as plt

plt.style.use('default')
# Generate some random Points
num_points = 20
points = np.random.uniform(-10, 10, (num_points, 2))
# Calculate the distance matrix
dist_mat = distance_matrix(points, points)

# Fill diagonal with 9999
np.fill_diagonal(dist_mat, 9999)
# Bool variable indicating if the point is used on the route or not
c = cvx.Variable((num_points, num_points), boolean = True)
# A variable useful for subtour elimination
u = cvx.Variable(num_points)
# Objective function - Minimize distance
obj = cvx.Minimize(sum([dist_mat[i,:] @ c[:,i] for i in range(num_points)]))
constraints = []
# Only 1 incoming connection for each node
for i in range(num_points):
    constraints.append(cvx.sum(c[i,:]) == 1) 

# Only 1 outbound connection for each node
for j in range(num_points):
    constraints.append(cvx.sum(c[:,j]) == 1) 
# Subtour elimination
for i in range(1, num_points):
    for j in range(1, num_points):
        if i != j:
            constraints.append(u[i] - u[j] + num_points * c[i,j] <= num_points - 1)
prob = cvx.Problem(obj, constraints)
opt = prob.solve()
# Get the route matrix
route_mat = np.around(c.value)
# Get the optimal tour
idx = 0
optimal_tour = []
optimal_tour.append(points[0].tolist())
for i in range(route_mat.shape[0]):
    idx = np.where(route_mat[idx, :]>= 0.99)[0][0]
    optimal_tour.append(points[idx].tolist())
optimal_tour = np.array(optimal_tour)
# Creates a figure and one subplot
fig, ax = plt.subplots(figsize=(9, 9))

# Plot the optimal tour
xcoords = optimal_tour[:,0]
ycoords = optimal_tour[:,1]
u = np.diff(xcoords)
v = np.diff(ycoords)
pos_x = xcoords[:-1] + u/2
pos_y = ycoords[:-1] + v/2

ax.quiver(pos_x, pos_y, u, v, color="lightgrey",
          angles='xy', scale_units='xy', scale=1, pivot='mid')

# Plot the points
ax.scatter(optimal_tour[:,0], optimal_tour[:,1], c='blue', marker = 'o')

# Annotate the lines with a progressive number
for i, x_i in enumerate(pos_x):
    ax.annotate(i+1, xy=(x_i, pos_y[i]), ha="center", va="center")

# Plot the start point
ax.scatter(optimal_tour[0][0], optimal_tour[0][1], s=250, 
           c=np.array([[0,0,0,0]]), edgecolors='red')

# Show the plot
ax.set_aspect('equal', adjustable='datalim')
plt.show()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.14519268197742313, 'fraction_numerical': 0.020630595562475672, 'mean_word_length': 4.309917355371901, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 6, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '324610', 'license': 'CC-BY-4.0', 'n_tokens_mistral': 1012, 'n_tokens_neox': 951, 'n_words': 238, 'path': 'LP/01_tsp.ipynb', 'repo_name': 'enricocid/python_gis', 'size': '2569'}