0
我是一般的新手，喜歡PuLP和LP。雖然translating the code意思是gurobipi庫，所以它可以與PuLP一起使用，但我被困在以下創建變量的gurobipy代碼中。將Python代碼從gurobipy翻譯成Python中的PuLP
# Create variables.
# x[i, j] is 1 if the edge i->j is on the optimal tour, and 0 otherwise.
x = {}
for i in range(n):
for j in range(i+1):
x[i,j] = m.addVar(obj=dist[i][j], vtype=GRB.BINARY,
name='x'+str(i)+'_'+str(j))
x[j,i] = x[i,j]
m.addVar允許USIG的obj參數定義的目標係數。如何在PuLP中完成相同的操作？它的docs for pulp.LpVariable似乎沒有一個類似的參數...
此外，有沒有任何示例代碼來解決在Python中使用PuLP的TSP？這將有助於很多參考！
這是我的代碼到目前爲止，沒有看subtours。決策變量x_ij的結果似乎是非常錯誤的，僅當i == j等於1.0。我的嘗試迄今爲止是否正確？
結果
0_0: 1.0
0_5: 1.0
1_1: 1.0
1_15: 1.0
2_2: 1.0
2_39: 1.0
3_3: 1.0
3_26: 1.0
4_4: 1.0
4_42: 1.0
5_5: 1.0
5_33: 1.0
6_6: 1.0
6_31: 1.0
7_7: 1.0
7_38: 1.0
8_8: 1.0
8_24: 1.0
9_9: 1.0
9_26: 1.0
10_4: 1.0
10_10: 1.0
11_11: 1.0
11_12: 1.0
12_11: 1.0
12_12: 1.0
13_13: 1.0
13_17: 1.0
14_14: 1.0
14_18: 1.0
15_1: 1.0
15_15: 1.0
16_3: 1.0
16_16: 1.0
17_13: 1.0
17_17: 1.0
18_14: 1.0
18_18: 1.0
19_19: 1.0
19_20: 1.0
20_4: 1.0
20_20: 1.0
21_21: 1.0
21_25: 1.0
22_22: 1.0
22_27: 1.0
23_21: 1.0
23_23: 1.0
24_8: 1.0
24_24: 1.0
25_21: 1.0
25_25: 1.0
26_26: 1.0
26_43: 1.0
27_27: 1.0
27_38: 1.0
28_28: 1.0
28_47: 1.0
29_29: 1.0
29_31: 1.0
30_30: 1.0
30_34: 1.0
31_29: 1.0
31_31: 1.0
32_25: 1.0
32_32: 1.0
33_28: 1.0
33_33: 1.0
34_30: 1.0
34_34: 1.0
35_35: 1.0
35_42: 1.0
36_36: 1.0
36_47: 1.0
37_36: 1.0
37_37: 1.0
38_27: 1.0
38_38: 1.0
39_39: 1.0
39_44: 1.0
40_40: 1.0
40_43: 1.0
41_41: 1.0
41_45: 1.0
42_4: 1.0
42_42: 1.0
43_26: 1.0
43_43: 1.0
44_39: 1.0
44_44: 1.0
45_15: 1.0
45_45: 1.0
46_40: 1.0
46_46: 1.0
47_28: 1.0
47_47: 1.0
...
紙漿代碼
def get_dist(tsp):
with open(tsp, 'rb') as tspfile:
r = csv.reader(tspfile, delimiter='\t')
d = [row for row in r]
d = d[1:] # skip header row
locs = set([r[0] for r in d]) | set([r[1] for r in d])
loc_map = {l:i for i, l in enumerate(locs)}
idx_map = {i:l for i, l in enumerate(locs)}
dist = [(loc_map[r[0]], loc_map[r[1]], r[2]) for r in d]
return dist, idx_map
def dist_from_coords(dist, n):
points = []
for i in range(n):
points.append([0] * n)
for i, j, v in dist:
points[i][j] = points[j][i] = float(v)
return points
def find_tour():
tsp_file = `/Users/test/` + 'my-waypoints-dist-dur.tsv'
coords, idx_map = get_dist(tsp_file)
n = len(idx_map)
dist = dist_from_coords(coords, n)
# Define the problem
m = pulp.LpProblem('TSP', pulp.LpMinimize)
# Create variables
# x[i,j] is 1 if edge i->j is on the optimal tour, and 0 otherwise
# Also forbid loops
x = {}
for i in range(n):
for j in range(n):
lowerBound = 0
upperBound = 1
# Forbid loops
if i == j:
upperBound = 0
print i,i
x[i,j] = pulp.LpVariable('x' + str(i) + '_' + str(j), lowerBound, upperBound, pulp.LpBinary)
x[j,i] = x[i,j]
# Define the objective function to minimize
m += pulp.lpSum([dist[i][j] * x[i,j] for i in range(n) for j in range(n)])
# Add degree-2 constraint
for i in range(n):
m += pulp.lpSum([x[i,j] for j in range(n)]) == 2
status = m.solve()
print pulp.LpStatus[status]
for i in range(n):
for j in range(n):
if pulp.value(x[i,j]) >0:
print str(i) + '_' + str(j) + ': ' + str(pulp.value(x[i,j]))
find_tour()
我的航點 - 距離 - dur.tsv(Full version)
waypoint1 waypoint2 distance_m duration_s
Michigan State Capitol, Lansing, MI 48933 Rhode Island State House, 82 Smith Street, Providence, RI 02903 1242190 41580
Minnesota State Capitol, St Paul, MN 55155 New Mexico State Capitol, Santa Fe, NM 87501 1931932 64455
跳過目標爲beeing變量的一部分，只是制定一個經典的優化功能（我用gurobi很多，從來沒有使用過）！還有，你爲什麼需要這個？像這樣寫的TSP解決方案將比較複雜的optimi慢zed方法。 （我曾經爲[cvxpy]編寫了一個簡單的TSP配方（https://github.com/cvxgrp/cvxpy/blob/master/examples/tsp_mip.py）來測試我的cbc接口）。它遵循維基百科的制定，並且比鏈接更緊湊。 – sascha
@sascha根據您的建議，我遵循基於維基百科的配方。用新代碼更新了問題。我不知道什麼是錯的......任何想法？ – Nyxynyx
你爲什麼不從一個只有距離的4節點案例開始？測試水。 – mengg