如何将 Gurobi Traveling Salesman Problem Python 代码应用于我的数据

Question

我想将来自 Gurobi 网站的示例旅行商问题 Python 代码与我的数据文件一起使用。我正在为如何操作我的数据的 df 以便将其合并到 Gurobi 代码中而苦苦挣扎。我对 Python 还是个新手，最近刚接触 Gurobi。

我从 Gurobi 网站上拉取了 TSP 示例代码并将其下载到运行。该示例创建随机点并计算它们之间的距离以说明 TSP 问题。我的电子表格中已经有了点和距离，它已作为 df 导入。我似乎无法将我的 df 转换为 Python 中的正确格式以供代码使用。似乎我需要将我的 df 转换为字典，其中包含每对可能的组合及其距离，但我不知道这样做的简单方法。

这是为示例创建虚拟数据的代码部分。我注释掉了我正在玩一个小的 df 数据来模拟我的文件的部分。

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'])

我希望能够将我的数据的 df 与 Gurobi TSP Python 代码一起使用。预先感谢您的帮助。

Answer 1

我之前在 Gurobi discussion board 上回答过这个问题。为了方便起见，我在这里重新发布（并详细说明）答案：

addVars 不直接接受 DataFrame。如果您的数据位于 DataFrame df 中，您可以执行以下操作：

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

tsp.py example code假设距离矩阵是对称的。例如，您可以从以下几行中看到这一点：

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

您需要删除这些以使其适用于非对称矩阵。

此外，您应该用确保每个节点只有一个传入和传出边的约束替换 2 阶约束。即，替换

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

来自

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

对于惰性约束，您需要确保添加每条边的两个方向。添加惰性约束应该如下所示：

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

如何将 Gurobi Traveling Salesman Problem Python 代码应用于我的数据

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

python

dictionary

traveling-salesman

pandas

gurobi