私は一般的に PuLP と LP は初めてです。ライブラリ用のコードをで使用できるように翻訳しているときに、変数を作成する次の gurobipy コードで立ち往生しています。gurobipiPuLP
# 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 を解決するためのサンプル コードはありますか? とても参考になります！
サブツアーを見ずに、これまでのコードを次に示します。決定変数の結果は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
...
PuLP コード
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