Problem in R studio while solving Traveling Salesman Problem (TSP) using Concorde
I am working with Concorde to solve TSP problems. Here is my code
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)
The Concorde is properly installed on my system and working fine. When I run concorde_help(), I get the following output
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
This shows that Concorde is installed properly. However, when I try to run the R code (which is given at the top), I get the answer sometimes, while sometimes my program gets stuck. When the program is executed successfully, I get the following output
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)
In the above output, the Optimal Solution is 0.00. Can anyone tell me why is this zero? Also sometimes the code does not execute and give the following output
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
After this output, nothing happens and program seems to go into an infinite loop. Can anyone tell me what am I doing wrong?
Is that the fault of my system? I am working on core i3 system with Windows 10 and R-studio 64 bit.
Edit: Here is the dataset which I am using
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
Edit 2: Here is the 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
2 ответа
Решение
Созданная вами матрица расстояний - это проблема для 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)
Надеюсь, это поможет.
Итак, я скомпилировал код и обнаружил, что существует проблема размерности с высокой размерной матрицей смежности. Вот мой последний код, чтобы справиться с этим сценарием.
Поскольку расстояние становится бессмысленным в больших измерениях, функция 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)
Надеюсь, это развеет сомнения, если таковые имеются.