一般来说，我是纸浆和 LP 的新手。在翻译用于gurobipi库的代码以便它可以与 一起使用时PuLP，我陷入了以下创建变量的 gurobipy 代码。
# 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允许使用参数定义目标系数obj。怎么能做同样的事情PuLP？它的文档pulp.LpVariable似乎没有类似的参数......
另外，是否有任何示例代码可以使用 PuLP 在 Python 中解决 TSP？作为参考，这将有很大帮助！
到目前为止，这是我的代码，没有查看 subtours。决策变量的结果x_ij似乎非常错误，1.0只有当 时才相等i == j。到目前为止我的尝试是否正确？
结果
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()
my-waypoints-dist-dur.tsv (完整版)
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