Comparing the Simulated Annealing and Robust Tabu Search Solvers

Introduction

The qap package provides two heuristics for the quadratic assignment problem (QAP), selected with the method argument of qap():

This vignette compares them on QAPLIB instances of increasing size, looking at the run time and at the quality of the solution. Quality is the percentage by which the objective value is above the known optimal (or best known) value stored with the instance.

Run times depend on your machine and the results depend on the random seed, so your numbers will differ from those shown here. Each comparison below is a single seeded run on a small set of instances, so it illustrates typical behavior rather than being a rigorous benchmark.

library(qap)
set.seed(2024)

Comparison

We solve instances with 30 to 100 facilities from QAPLib. Each method gets 3 random restarts and uses its default settings.

instances <- c("tai30a", "tai50a", "tai80a", "sko100a")
reps <- 3

run <- function(p, method, ...) {
  time <- system.time(a <- qap(p$A, p$B, method = method, ...))[["elapsed"]]
  c(obj = unname(attr(a, "obj")), time = time)
}

res <- do.call(rbind, lapply(instances, function(f) {
  p <- read_qaplib(system.file("qaplib", paste0(f, ".dat"), package = "qap"))
  sa <- run(p, "SA", rep = reps)
  ro <- run(p, "RoTS", rep = reps)
  data.frame(
    instance = f,
    n = nrow(p$A),
    opt = p$opt,
    SA_gap = (sa[["obj"]] - p$opt) / p$opt * 100,
    RoTS_gap = (ro[["obj"]] - p$opt) / p$opt * 100,
    SA_time = sa[["time"]],
    RoTS_time = ro[["time"]]
  )
}))
knitr::kable(res, digits = 3, row.names = FALSE,
  col.names = c("Instance", "n", "Optimum", "SA gap (%)", "RoTS gap (%)",
                "SA time (s)", "RoTS time (s)"))
Instance n Optimum SA gap (%) RoTS gap (%) SA time (s) RoTS time (s)
tai30a 30 1818146 4.495 0.000 0.001 0.055
tai50a 50 4938796 5.799 1.475 0.002 0.226
tai80a 80 13499184 4.147 1.370 0.006 0.916
sko100a 100 152002 1.457 0.141 0.019 1.813 
op <- par(mfrow = c(1, 2), mar = c(4, 4, 2, 1))
matplot(res$n, res[, c("SA_gap", "RoTS_gap")], type = "b", pch = 1:2,
        lty = 1, col = 1:2, xlab = "n", ylab = "gap above optimum (%)",
        main = "Solution quality")
legend("topleft", legend = c("SA", "RoTS"), pch = 1:2, col = 1:2, lty = 1)
matplot(res$n, res[, c("SA_time", "RoTS_time")], type = "b", pch = 1:2,
        lty = 1, col = 1:2, log = "y", xlab = "n", ylab = "seconds",
        main = "Run time")

Solution gap and run time of both solvers by instance size.

par(op)

Simulated annealing finishes much faster, but its solutions are typically further from the optimum. The solution can be modestly improved by tuning (increasing) ft and maxsteps.

Robust tabu search spends more time and finds better solutions. Its cost per iteration grows with the number of swap moves, which is quadratic in n, and its default number of iterations grows linearly with n. Its run time therefore grows roughly cubically with n.

Larger QAPLIB instances such as tai256c (256 facilities) can be added to instances, but a single tabu search restart then takes tens of seconds, so we leave them out to keep this vignette fast to build.

Recommendations

References