How to apply Gurobi Traveling Salesman Problem Python code to my data

Question

I would like to use the example Traveling Salesman Problem Python code from the Gurobi website with my data file. I'm struggling with how to manipulate the df of my data so that it can be incorporated into the Gurobi code. I'm still fairly new to Python and I've just recently been introduced to Gurobi.

I pulled the TSP example code from the Gurobi website and got it to run. The example creates random points and calculates the distances between them to illustrate the TSP problem. I already have the points and distances in my spreadsheet, which has been imported as a df. I can't seem to get my df into the right format in Python for the code to use. It seems like I need to convert my df to a dictionary with each possible combination of pairs and their distance, but I don't know an easy way to do that.

Here's the the section of code that creates dummy data for the example. I commented out the part where I was playing with a small df of data to simulate my file.

import math
import random
from gurobipy import *

# Euclidean distance between two points 

def distance(points, i, j): 
    dx = points[i][0] - points[j][0] 
    dy = points[i][1] - points[j][1] 
    return math.sqrt(dx*dx + dy*dy)

n=50

# Create n random points 

random.seed(1) 
points = [] 
for i in range(n): 
    points.append((random.randint(0,100),random.randint(0,100))) 

m = Model() 

# Create variables 

vars = {} 
for i in range(n): 
    for j in range(i+1): 
        vars[i,j] = m.addVar(obj=distance(points, i, j), vtype=GRB.BINARY, name='e'+str(i)+'_'+str(j)) 
        vars[j,i] = vars[i,j] 
    m.update()

#Attempting to incorporate my own data
#import pandas as pd
#data = [[0,20,15,8,6],[15,0,18,9,28],[24,23,0,13,13],[15,27,8,0,14],[8,17,24,15,0]]
#df = pd.DataFrame(data, columns=['P1','P2','P3','P4','P5'],index=['P1','P2','P3','P4','P5'])

I would like to be able to use a df of my data with the Gurobi TSP Python code. Thank you in advance for any help.

Answer 1

I have answered this question before on the Gurobi discussion board. For convenience I am reposting (and detailing) the answer here:

addVars does not directly accept a DataFrame. If you have your data in a DataFrame df, you could do the following:

n=df.shape[0]
dist = {(i,j) : df.iloc[i][j] for i in range(n) for j in range(n) if i != j}

The tsp.py example code assumes that the distance matrix is symmetrical. You can see this for example from the lines:

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

You need to remove these to make it work with an asymmetrical matrix.

Moreover, you should replace the degree 2 constraints by constraints that ensure that every node has exactly one incoming and outgoing edge. I.e., replace

m.addConstrs(vars.sum(i,'*') == 2 for i in range(n))

by

m.addConstrs(vars.sum(i,'*') == 1 for i in range(n))
m.addConstrs(vars.sum('*',i) == 1 for i in range(n))

For the lazy constraints, you need to make sure that both directions of each edge are added. Adding the lazy constraint should then look like this:

        model.cbLazy(quicksum(model._vars[i,j] + model._vars[j,i]
                              for i,j in itertools.combinations(tour, 2))
                     <= len(tour)-1)