0
저는 PuLP와 LP를 일반적으로 사용하고 있습니다. 은 gurobipi 라이브러리를 의미하므로 PuLP과 함께 사용할 수 있습니다. 변수를 만드는 다음과 같은 거미집 코드가 붙어 있습니다.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 대물 계수가 obj usig 파라미터를 정의 할 수있다. PuLP에서 어떻게 동일한 작업을 수행 할 수 있습니까? docs for pulp.LpVariable에는 비슷한 매개 변수가없는 것 같습니다 ...
또한 PuLP를 사용하여 Python으로 TSP를 해결하는 예제 코드가 있습니까? 그것은 참고로 많은 도움이 될 것입니다!
하위 코드를 보지 않고 여기까지입니다. 의사 결정 변수 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-solver는 매우 복잡한 optimizer와 비교할 때 속도가 느릴 것입니다. 접근 방식. (필자는 내 cbc 인터페이스 테스트를 위해 [cvxpy] (https://github.com/cvxgrp/cvxpy/blob/master/examples/tsp_mip.py)에 대한 간단한 TSP 공식을 코딩했습니다. 그것은 위키피디아의 공식화를 따르며 링크에 비해 훨씬 더 컴팩트합니다. – sascha
@ sacha 귀하의 제안에 따라, 나는 Wikipedia에 기초한 공식을 따르고 있습니다. 질문을 새 코드로 업데이트했습니다. 나는 틀린 것을 계산할 수 없다. .. 어떤 생각? – Nyxynyx
거리가 4 노드 인 경우부터 시작한 이유가 무엇입니까? 물 시험. – mengg