Skip to content

Instantly share code, notes, and snippets.

# dirkschumacher/benchmark-tsp.R Last active Dec 3, 2017

 # There are essential two prominent ways to model a TSP as a MILP. One is to formulate the full model using the Miller–Tucker–Zemlin (MTZ) formulation and the other option is to use the so-called sub-tour elimination constraints .(https://www.unc.edu/~pataki/papers/teachtsp.pdf) # # The first formulation is fairly compact (quadratic many constraints and variables) but is not suitable anymore when n gets larger. The second formulation has exponential many constraints at most, but can solve larger TSPs due to the better LP relaxation. The idea of the latter approach is add constraints to the model *during* the solution process as soon as a solution was found that contains a sub-tour. For solution strategies like this solvers usually offer callbacks that let's you modify the model during the the branch-and-cut process - this is however not currently supported by `ompr`. # # Therefor we will use the MTZ formulation and solve a fairly small TSP. library(ompr) library(magrittr) dist_fun <- function(i, j) { 1 # make it constant so it does not affect the modelbuilding } n <- 1000 system.time({ model <- MILPModel() %>% # we create a variable that is 1 iff we travel from city i to j add_variable(x[i, j], i = 1:n, j = 1:n, type = "integer", lb = 0, ub = 1) %>% # a helper variable for the MTZ formulation of the tsp add_variable(u[i], i = 1:n, lb = 1, ub = n) %>% # minimize travel distance set_objective(sum_expr(colwise(dist_fun(i, j)) * x[i, j], i = 1:n, j = 1:n), "min") %>% # you cannot go to the same city set_bounds(x[i, i], ub = 0, i = 1:n) %>% # leave each city add_constraint(sum_expr(x[i, j], j = 1:n) == 1, i = 1:n) %>% # # visit each city add_constraint(sum_expr(x[i, j], i = 1:n) == 1, j = 1:n) %>% # ensure no subtours (arc constraints) add_constraint(u[i] >= 2, i = 2:n) %>% add_constraint(u[i] - u[j] + 1 <= (n - 1) * (1 - x[i, j]), i = 2:n, j = 2:n) }) model
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.