Как применить код Python кода Gurobi Traveling Salesman к моим данным - PullRequest
Новая
       20

Как применить код Python кода Gurobi Traveling Salesman к моим данным

0 голосов
/ 14 февраля 2019

Я хотел бы использовать пример кода Python для командировочного коммивояжера с веб-сайта Gurobi с моим файлом данных.Я борюсь с тем, как манипулировать df моих данных, чтобы они могли быть включены в код Gurobi.Я все еще довольно новичок в Python и только недавно познакомился с Gurobi.

Я взял пример кода TSP с веб-сайта Gurobi и запустил его.В этом примере создаются случайные точки и вычисляются расстояния между ними, чтобы проиллюстрировать проблему 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 моих данных с кодом Python Gurobi TSP.Заранее благодарю за любую помощь.

1 Ответ

0 голосов
/ 28 февраля 2019

Я уже отвечал на этот вопрос ранее на доске объявлений Gurobi .Для удобства я публикую (и подробно) ответ здесь:

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 предполагает, что матрица расстояний симметрична.Это видно, например, из строк: 

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)
...