Определение модели линейного программирования для путешествующего коммивояжера в Python

Использование библиотеки Python и PuLP, как мы можем создать модель линейного программирования для решения проблемы Traveling Salesman (TSP)?Определение модели линейного программирования для путешествующего коммивояжера в Python

Материал из Википедии целевая функция и ограничения

Проблема: Вот моя частичная попытка, где я застрял.

Я не включил окончательное ограничение в код, потому что я не знаю, как его определить. Я считаю, что это ограничение с и переменных для предотвращения вложенных циклов в растворе
Кроме того, решение для текущей модели дает переменные решения, такие как x0_0 и x1_1 равна 1.0 который, безусловно, не так ... Я могу» т понять, почему это так, хотя я был
```
if i == j: 
     upperBound = 0 
```

Python код

import 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 


    # Solve and display results 
    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

Файл can be found here данных.

Результат

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 



...

Обновленный код

import csv 
import 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+1): 
     for j in range(n+1): 
      lowerBound = 0 
      upperBound = 1 

      # Forbid loops 
      if i == j: 
       upperBound = 0 
       # print i,i 

      # Create the decision variable and First constraint 
      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(1,n+1) for j in range(1,n+1)]) 


    # Add degree-2 constraint (3rd and 4th) 
    for i in range(1,n+1): 
     m += pulp.lpSum([x[i,j] for j in range(1,n+1)]) == 2 


    # Add the last (5th) constraint (prevents subtours) 
    u = [] 
    for i in range(1, n+1): 
     u.append(pulp.LpVariable('u_' + str(i), cat='Integer')) 
    for i in range(1, n-1): 
     for j in range(i+1, n+1): 
      m += pulp.lpSum([ u[i] - u[j] + n*x[i,j]]) <= n-1 


    # 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()

источник

2016-10-06 Nyxynyx

Какая проблема у вас есть с кодом? – kindall

@kindall Я не включил последнее ограничение, потому что я не знаю, как его определить. Кроме того, решение для текущей модели дает такие переменные решения, как 'x1_1', равные' 1.0', что определенно неверно ... Я не могу понять, почему это так. – Nyxynyx

@kindall Обновлен вопрос, чтобы прояснить проблему и включил неверные результаты в текущий код. – Nyxynyx

Последнее ограничение не одно ограничение. Вы должны добавить одно ограничение для каждой пары индексов i, j что удовлетворяет этому условию:

for i in range(n-1): 
    for j in range(i+1, n): 
     m += pulp.lpSum([ u[i] - u[j] + n*x[i,j]]) <= n-1

Однако вы должны сначала объявить u_i переменные как целые числа, передавая cat='Integer' аргумент в LpVariable:

u = [] 
for i in range(n): 
    u.append(pulp.LpVariable('u_' + str(i), cat='Integer'))

источник

2016-10-06 06:17:42 Bakuriu

Спасибо, я изучаю ваше предложение. До сих пор текущий код выглядит нормально? Является ли недостаток последнего ограничения причиной 'x0_0',' x1_1' и т. Д., Чтобы получить значения '1.0' вместо' 0.0'? – Nyxynyx

@Nyxynyx Последнее ограничение является абсолютно фундаментальным для проблемы. Без него проблема не является даже * целочисленной * линейной проблемой, а просто линейной проблемой и, как таковая, не может представлять TSP каким-либо значимым образом (помните, что TSP не может быть разрешен за полиномиальное время и даже не может быть аппроксимирован «хорошим способом» «в полиномиальное время, поэтому каждая нецелочисленная проблема линейного программирования (которая всегда может быть решена в полиномиальное время) не может представлять ее или какое-либо хорошее приближение) – Bakuriu

Поскольку я пытаюсь ассимилировать код для последнего ограничения, я добавил их к текущему коду и попытался решить для него, но результаты по-прежнему выглядят странно, получая значения '1.0' для переменных' x [i, j] 'где' i == j'. – Nyxynyx

Определение модели линейного программирования для путешествующего коммивояжера в Python

ответ

Смежные вопросы