reformulate_ATSP_as_TSP behaviour

[RegularnaMatrica]

I need some clarification on reformulate_ATSP_as_TSP. It seems to me that reformulate_ATSP_as_TSP extends in 'transposed' way. Take following matrix for example:

m <- structure(c(1, 640, 216, 382, 105, 750, 1, 626, 413, 696, 247, 
616, 1, 353, 233, 578, 497, 440, 1, 513, 80, 712, 297, 468, 1
), .Dim = c(5L, 5L))

Using concorde:

sol <- m %>%
    ATSP() %>%
    reformulate_ATSP_as_TSP(cheap = 0, infeasible = max(m)) %>%
    insert_dummy() %>%
    solve_TSP(method = "concorde")

object of class ‘TOUR’ 
result of method ‘concorde’ for 10 cities
tour length: 1146 

point order:

 cut_tour(sol, "dummy") %>%
    .[. <= nrow(m)]

5 1 3 4 2 

and calculate tour length:

cut_tour(sol, "dummy") %>%
    .[. <= nrow(m)] %>%
    embed(2) %>%
    .[, 2:1] %>%
    m[.] %>%
    sum()

1205

I get different tour length. Changing 2:1 to 1:2 in embed would give me correct length but that is not as it should be. If I take reformulated matrix:

mm <- m %>%
    ATSP() %>%
    reformulate_ATSP_as_TSP(cheap = 0, infeasible = max(m))

and calculate length:

sol %>% 
 cut_tour("dummy") %>% 
 embed(2) %>% 
 .[,2:1] %>% 
 mm[.] %>% 
 sum()

1146

I get correct length. Is this expected behaviour or values in extended matrix between cites and dummies is 'transposed'?

[mhahsler]

I think the issue is that you are calculating the length in two different directions. Here is how I would do this. This requires the latest version of TSP (see: https://mhahsler.r-universe.dev/ui#package:TSP)

library(TSP)
library(tidyverse)

m <- structure(c(1, 640, 216, 382, 105, 750, 1, 626, 413, 696, 247,
    616, 1, 353, 233, 578, 497, 440, 1, 513, 80, 712, 297, 468, 1
   ), .Dim = c(5L, 5L))
m

Add the dummy first and then reformulate as a TSP. The dummy has distance 0, so I have to set cheap to a value smaller than that.

atsp <- m %>% ATSP() %>% insert_dummy()

tsp <- atsp %>%
  reformulate_ATSP_as_TSP(cheap = -1)

Solve with Concorde

sol <- tsp %>% solve_TSP(method = "concorde")
tour_length(sol)
names(sol)

The latest development version of TSP (to be released as TSP_1.2.1) has a filter function that converts the TSP solution back to an ATSP solution for the original problem. It takes care of the direction of the path.

tour <- filter_ATSP_as_TSP_dummies(sol, atsp)
tour
names(tour)

Cut at the dummy.

tour <- cut_tour(tour, "dummy")
names(tour)

You can now check the path length manually.

m[tour, tour]
80 + 216 + 353 + 497

BTW, you could also skip the reformulation and dummy city filtering with as_TSP

atsp %>% solve_TSP(method = "concorde", as_TSP = TRUE)

Let me know if this works.

regards, -MFH