Перевод кода Python из gurobipy в PuLP в Python

Я новичок в PuLP и 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 похоже не имеет аналогичного параметра...

Кроме того, есть ли пример кода для решения TSP в Python с использованием PuLP? Это очень поможет в качестве справки!

Вот мой код до сих пор, не глядя на 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



...

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
Источник

1 ответ

При создании переменных:

  • Изменено имя переменной, чтобы она была немного более питонна при форматировании
  • x[j,i] = x[i,j] это неверно. Это концепция ссылок Python. Все объекты в Python имеют ссылку, и когда вы назначаете одну переменную двум именам x[i,j] и x[j,i], это приводит к тому, что оба они указывают на один и тот же объект. Если вы измените x[i,j] в своей формулировке, x[j,i] также изменится.

С точки зрения проблемы коммивояжера, это означает, что если вы переходите от A ->B (то есть x[A][B] == 1, то вы также путешествуете от B ->A. Именно поэтому вы получаете бесконечный 1.0 значения в ваших переменных пути.

Исправленное определение переменной тогда становится:

x[i,j] = pulp.LpVariable('x_%s_%s'%(i,j), lowerBound, upperBound, pulp.LpBinary)
x[j,i] = pulp.LpVariable('x_%s_%s'%(j,i), lowerBound, upperBound, pulp.LpBinary)
Источник
Другие вопросы по тегам