Проблема в R studio при решении задачи коммивояжера (TSP) с помощью Concorde

Question

Я работаю с Concorde для решения проблем TSP. Вот мой код

library(TSP)

concordePath = "E:/Concorde_Code/"
concorde_path(concordePath)
concorde_help()


dataset_path = "E:/RA/"
name = "graph1.txt"
dataset = read.table(paste(dataset_path,name,sep = ""))

arr=dataset
nodelist = unique(as.vector(as.matrix(arr)))
arr_mat = matrix(0,length(nodelist),length(nodelist))
for (i in 1:length(arr[,1])){
  arr_mat[arr[i,1],arr[i,2]] = 1
  arr_mat[arr[i,2],arr[i,1]] = 1
}
arr_mat_new = arr_mat
for(i in 1:length(arr_mat[,1])){
  arr_mat_new[i,which(arr_mat[i,]==0)] = 2 #replace all zero entries with 2
}

d <- as.dist(arr_mat_new)
tsp <- TSP(d)
tsp

o <- solve_TSP(tsp, method="concorde")
labels(o)

Concorde правильно установлен в моей системе и работает нормально. Когда я запускаю concorde_help (), я получаю следующий вывод

The following options can be specified in solve_TSP with method "concorde" using clo in control:
/Concorde_Code/concorde
Usage: /Concorde_Code/concorde [-see below-] [dat_file]
   -B    do not branch
   -C #  maximum chunk size in localcuts (default 16)
   -d    use dfs branching instead of bfs
   -D f  edgegen file for initial edge set
   -e f  initial edge file
   -E f  full edge file (must contain initial edge set)
   -f    write optimal tour as edge file (default is tour file)
   -F f  read extra cuts from file
   -g h  be a grunt for boss h
   -h    be a boss for the branching
   -i    just solve the blossom polytope
   -I    just solve the subtour polytope
   -J #  number of tentative branches
   -k #  number of nodes for random problem
   -K h  use cut server h
   -M f  master file
   -m    use multiple passes of cutting loop
   -n s  problem location (just a name or host:name, not a file name)
   -o f  output file name (for optimal tour)
   -P f  cutpool file
   -q    do not cut the root lp
   -r #  use #x# grid for random points, no dups if #<0
   -R f  restart file
   -s #  random seed
   -S f  problem file
   -t f  tour file (in node node node format)
   -u v  initial upperbound
   -U    do not permit branching on subtour inequalities
   -v    verbose (turn on lots of messages)
   -V    just run fast cuts
   -w    just subtours and trivial blossoms
   -x    delete files on completion (sav pul mas)
   -X f  write the last root fractional solution to f
   -y    use simple cutting and branching in DFS
   -z #  dump the #-lowest reduced cost edges to file xxx.rcn
   -N #  norm (must specify if dat file is not a TSPLIB file)
         0=MAX, 1=L1, 2=L2, 3=3D, 4=USER, 5=ATT, 6=GEO, 7=MATRIX,
         8=DSJRAND, 9=CRYSTAL, 10=SPARSE, 11-15=RH-norm 1-5, 16=TOROIDAL
         17=GEOM, 18=JOHNSON

Это показывает, что Concorde установлен правильно. Однако, когда я пытаюсь запустить код R (который дан вверху), я иногда получаю ответ, а иногда моя программа застревает. Когда программа выполнена успешно, я получаю следующий вывод

Used control parameters:
clo  =  
exe  =  E:\Concorde_Code\/concorde
precision    =  6
verbose  =  TRUE
keep_files   =  FALSE
/Concorde_Code/concorde -x -o file18ec719b5412.sol file18ec719b5412.dat
Host: Pasha  Current process id: 1165
Using random seed 1586633006
Problem Name: TSP
Generated by write_TSPLIB (R-package TSP)
Problem Type: TSP
Number of Nodes: 66
Explicit Lengths (CC_MATRIXNORM)
Set initial upperbound to 0 (from tour)
  LP Value  1: 0.000000  (0.03 seconds)
New lower bound: 0.000000
WARNING: LK incremental counter was off by 4294967296
Final lower bound 0.000000, upper bound 0.000000
Exact lower bound: 0.000000
DIFF: 0.000000
Final LP has 71 rows, 129 columns, 345 nonzeros
Optimal Solution: 0.00
Number of bbnodes: 1
Total Running Time: 1.70 (seconds)

В приведенном выше выводе оптимальное решение равно 0,00. Может кто-нибудь сказать мне, почему это ноль? Также иногда код не выполняется и выдает следующий вывод

Used control parameters:
clo  =  
exe  =  E:\Concorde_Code\/concorde
precision    =  6
verbose  =  TRUE
keep_files   =  FALSE
/Concorde_Code/concorde -x -o file18ec7f123355.sol file18ec7f123355.dat
Host: Pasha  Current process id: 693
Using random seed 1586633314
FATAL ERROR - received signal SIGSEGV (11/11)
Problem Name: TSP
Generated by write_TSPLIB (R-package TSP)
Problem Type: TSP
Number of Nodes: 66
Explicit Lengths (CC_MATRIXNORM)
sleeping 1 more hours to permit debugger access

После этого вывода ничего не происходит, и программа кажется go в бесконечном l oop. Может кто-нибудь сказать мне, что я делаю не так?

Это вина моей системы? Я работаю на системе Core i3 с Windows 10 и R-studio 64 бит.

Редактировать: вот набор данных, который я использую

   V1 V2
1   1  3
2   1  9
3   1 61
4   2 17
5   2 31
6   2 51
7   3 40
8   3 46
9   4 42
10  4 47
11  4 63
12  5  8
13  5 18
14  5 39
15  6 30
16  6 40
17  6 62
18  7 13
19  7 31
20  7 58
21  8 50
22  8 63
23  9 25
24  9 35
25 10 16
26 10 27
27 10 44
28 11 19
29 11 45
30 11 54
31 12 21
32 12 47
33 12 55
34 13 51
35 13 66
36 14 35
37 14 57
38 14 61
39 15 18
40 15 20
41 15 63
42 16 52
43 16 53
44 17 21
45 17 37
46 18 23
47 19 52
48 19 56
49 20 32
50 20 57
51 21 34
52 22 38
53 22 44
54 22 60
55 23 49
56 23 57
57 24 36
58 24 56
59 24 62
60 25 36
61 25 46
62 26 43
63 26 60
64 26 64
65 27 60
66 27 65
67 28 44
68 28 45
69 28 52
70 29 31
71 29 37
72 29 41
73 30 54
74 30 56
75 32 35
76 32 36
77 33 43
78 33 48
79 33 66
80 34 39
81 34 50
82 37 55
83 38 45
84 38 59
85 39 49
86 40 59
87 41 42
88 41 58
89 42 55
90 43 65
91 46 62
92 47 50
93 48 51
94 48 53
95 49 61
96 53 65
97 54 59
98 58 64
99 64 66

Редактировать 2: Вот sessioninfo

R version 3.5.2 (2018-12-20)
Platform: x86_64-w64-mingw32/x64 (64-bit)
Running under: Windows >= 8 x64 (build 9200)

Matrix products: default

locale:
[1] LC_COLLATE=English_United States.1252  LC_CTYPE=English_United States.1252   
[3] LC_MONETARY=English_United States.1252 LC_NUMERIC=C                          
[5] LC_TIME=English_United States.1252    

attached base packages:
[1] stats     graphics  grDevices utils     datasets  methods   base     

other attached packages:
[1] R.utils_2.9.2     R.oo_1.23.0       R.methodsS3_1.8.0 tspmeta_1.2       MASS_7.3-51.1    
[6] ggplot2_3.1.1     TSP_1.1-9        

loaded via a namespace (and not attached):
 [1] modeltools_0.2-22   tidyselect_0.2.5    xfun_0.4            purrr_0.2.5         kernlab_0.9-27     
 [6] lattice_0.20-38     colorspace_1.4-1    stats4_3.5.2        mgcv_1.8-26         yaml_2.2.0         
[11] rlang_0.3.4         pillar_1.4.1        glue_1.3.1          withr_2.1.2         prabclus_2.2-6     
[16] sp_1.3-1            fpc_2.1-11.1        bindrcpp_0.2.2      foreach_1.4.4       bindr_0.1.1        
[21] plyr_1.8.4          robustbase_0.93-3   stringr_1.4.0       munsell_0.5.0       gtable_0.3.0       
[26] mvtnorm_1.0-8       codetools_0.2-15    knitr_1.21          permute_0.9-5       parallel_3.5.2     
[31] flexmix_2.3-14      class_7.3-15        DEoptimR_1.0-8      trimcluster_0.1-2.1 Rcpp_1.0.1         
[36] backports_1.1.4     scales_1.0.0        diptest_0.75-7      checkmate_1.9.0     vegan_2.5-6        
[41] stringi_1.4.3       BBmisc_1.11         dplyr_0.7.8         splancs_2.01-40     grid_3.5.2         
[46] tools_3.5.2         magrittr_1.5        lazyeval_0.2.2      tibble_2.1.3        cluster_2.0.7-1    
[51] crayon_1.3.4        pkgconfig_2.0.2     Matrix_1.2-15       assertthat_0.2.1    rstudioapi_0.8     
[56] iterators_1.0.10    R6_2.4.0            mclust_5.4.2        nlme_3.1-137        nnet_7.3-12        
[61] compiler_3.5.2  

Answer 1

Созданная вами матрица расстояний является проблемой для Concorde. Concorde должен это уловить и выдать соответствующее сообщение об ошибке.

Вот подходящий способ преобразовать граф, представленный в виде списка ребер, в матрицу расстояний и решить TSP (используя версию TSP 1.1-10 или более позднюю):

library("igraph")
library("TSP")

# Read edgelist (you can use read.csv or read.table)
edgelist <- structure(list(V1 = c(1L, 1L, 1L, 2L, 2L, 2L, 3L, 3L, 4L, 4L, 
4L, 5L, 5L, 5L, 6L, 6L, 6L, 7L, 7L, 7L, 8L, 8L, 9L, 9L, 10L, 
10L, 10L, 11L, 11L, 11L, 12L, 12L, 12L, 13L, 13L, 14L, 14L, 14L, 
15L, 15L, 15L, 16L, 16L, 17L, 17L, 18L, 19L, 19L, 20L, 20L, 21L, 
22L, 22L, 22L, 23L, 23L, 24L, 24L, 24L, 25L, 25L, 26L, 26L, 26L, 
27L, 27L, 28L, 28L, 28L, 29L, 29L, 29L, 30L, 30L, 32L, 32L, 33L, 
33L, 33L, 34L, 34L, 37L, 38L, 38L, 39L, 40L, 41L, 41L, 42L, 43L, 
46L, 47L, 48L, 48L, 49L, 53L, 54L, 58L, 64L), V2 = c(3L, 9L, 
61L, 17L, 31L, 51L, 40L, 46L, 42L, 47L, 63L, 8L, 18L, 39L, 30L, 
40L, 62L, 13L, 31L, 58L, 50L, 63L, 25L, 35L, 16L, 27L, 44L, 19L, 
45L, 54L, 21L, 47L, 55L, 51L, 66L, 35L, 57L, 61L, 18L, 20L, 63L, 
52L, 53L, 21L, 37L, 23L, 52L, 56L, 32L, 57L, 34L, 38L, 44L, 60L, 
49L, 57L, 36L, 56L, 62L, 36L, 46L, 43L, 60L, 64L, 60L, 65L, 44L, 
45L, 52L, 31L, 37L, 41L, 54L, 56L, 35L, 36L, 43L, 48L, 66L, 39L, 
50L, 55L, 45L, 59L, 49L, 59L, 42L, 58L, 55L, 65L, 62L, 50L, 51L, 
53L, 61L, 65L, 59L, 64L, 66L)), class = "data.frame", row.names = c("1", 
"2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", 
"14", "15", "16", "17", "18", "19", "20", "21", "22", "23", "24", 
"25", "26", "27", "28", "29", "30", "31", "32", "33", "34", "35", 
"36", "37", "38", "39", "40", "41", "42", "43", "44", "45", "46", 
"47", "48", "49", "50", "51", "52", "53", "54", "55", "56", "57", 
"58", "59", "60", "61", "62", "63", "64", "65", "66", "67", "68", 
"69", "70", "71", "72", "73", "74", "75", "76", "77", "78", "79", 
"80", "81", "82", "83", "84", "85", "86", "87", "88", "89", "90", 
"91", "92", "93", "94", "95", "96", "97", "98", "99"))

# create graph
g <- graph_from_edgelist(as.matrix(edgelist), directed = FALSE)
plot(g)

# convert graph into a distance matrix
d <- as.dist((1/as_adjacency_matrix(g, sparse = FALSE))-1)

# solve TSP
tsp <- TSP(d)

# standard heuristic works, but uses a non-existing edge (path length is Inf)
o <- solve_TSP(tsp)
o
as.integer(o)


# Lin-Kernighan heuristic works, but also uses a non-existing edge (path length is Inf)
o <- solve_TSP(tsp, method="linkern")
o
as.integer(o)

# Concorde finds an optimal solution with path length 0
o <- solve_TSP(tsp, method="Concorde")
o
as.integer(o)

Надеюсь, это поможет.

Answer 2

Итак, я скомпилировал код и обнаружил, что существует проклятие проблемы размерности с высокомерной матрицей смежности. Вот мой окончательный код, чтобы справиться с этим сценарием.

Поскольку в больших измерениях расстояние становится бессмысленным, функция as.dist не работает эффективно для графа с большим числом узлов.

Вот мой последний рабочий код на случай, если кто-то захочет проверить это

dataset_path = "E:/RA/Pablo Moscato/dataset/FHCPCS/"
# name = "graph1.txt"  #Found
# name = "graph2.txt" #Found
name = "graph3.txt"
# name = "graph4.txt"
# name = "graph5.txt"
# name = "graph6.txt"  #Found
# name = "graph7.txt"
# name = "graph8.txt"
# name = "graph9.txt"
# name = "graph10.txt"
# name = "graph13.txt"
# name = "graph19.txt"
# name = "graph40.txt"
dataset = read.table(paste(dataset_path,name,sep = ""))
# main_function(dataset)

# create graph
# g <- graph_from_edgelist(as.matrix(dataset))
# plot(g)

final_edgelist = dataset

g <- graph_from_edgelist(as.matrix(final_edgelist))
# plot(g)

# convert graph into a distance matrix
adj_mat = as_adjacency_matrix(g, sparse = FALSE)
adj_mat_2 = adj_mat

nodelist = unique(as.vector(as.matrix(final_edgelist)))
adj_mat_sym = matrix(0,length(unique(nodelist)),length(unique(nodelist)))
for(i in 1:length(final_edgelist[,1])){
  adj_mat_sym[final_edgelist[i,1],final_edgelist[i,2]] = 1
  adj_mat_sym[final_edgelist[i,2],final_edgelist[i,1]] = 1
}


M = adj_mat_sym
lower_triangle = M[lower.tri(M)]
lower_triangle_2 = lower_triangle
lower_triangle_2[lower_triangle_2==0] = 2
lower_triangle_2[lower_triangle_2==1] = 0
lower_triangle_2[lower_triangle_2==2] = 100



d <- as.dist(1/(1+adj_mat_2))
d_5 = d
d_5[1:length(d_5)] = lower_triangle_2[1:length(lower_triangle_2)]
d_6 <- (1/(1+d_5))

d_7 = d_6
d_7[d_7==1] = 0

# tsp <- TSP(d_6)
tsp <- TSP(d_7)
# tsp_check <- TSP(d)

# o2 <- solve_TSP(tsp)
# o2
# as.integer(o2)


o2 <- solve_TSP(tsp, method="concorde",rep=10, control = list(clo = "-V"))
# o2 <- solve_TSP(tsp_check, method="concorde",rep=10, control = list(clo = "-V"))
o2
as.integer(o2)

Я надеюсь, что это устранит сомнения, если таковые имеются.