如何将Gurobi旅行商问题Python代码应用于我的数据

Question

我想使用Gurobi网站上的旅行商问题Python代码示例和我的数据文件。我正在努力如何操纵我的数据的df，以便它可以合并到Gurobi代码中。我仍然是Python的新手，我最近才被介绍给Gurobi。

我从Gurobi网站上获取了TSP示例代码并让它运行。该示例创建随机点并计算它们之间的距离以说明TSP问题。我的电子表格中已经有点和距离，它已作为df导入。我似乎无法将我的df在Python中用于正确的格式以供使用的代码。似乎我需要将我的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'])

我希望能够在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)