This is a report of the resolution of a sample of several quadratic assingment problem (QAP) instances of QAPLIB through several algorithms. In particular we will solve here:
To do so, we will use the functions in the QAPfunctions.R file to solve the QAP:
source("QAPfunctions.R")Then we are ready to read the files using the readQAPLIB function. In all instances distance matrix is reported first, except in the had instances so we have to use the function with swap=TRUE for these instances. Finally all inputs are stored in:
data list of 10 lists containing the flow and distance matrix of each instancesample vector containing the name of each instanceurl.base <- "http://www.opt.math.tu-graz.ac.at/qaplib/data.d/"
link <- function(x) paste0(url.base, x, ".dat")
sample.med <- c("rou12", "rou15", "rou20", "scr12", "scr15", "scr20")
link.med <- lapply(sample.med, link)
data.med <- lapply(link.med, read.QAPLIB)
names(data.med) <- sample.med
sample.tfda <- c("had12", "had16", "had18", "had20")
link.tfda <- lapply(sample.tfda, link)
data.tfda <- lapply(link.tfda, function(x) read.QAPLIB(x, swap="TRUE"))
names(data.tfda) <- sample.tfda
data <- c(data.med, data.tfda)
sample <- c(sample.med, sample.tfda)
rm(data.med, data.tfda, sample.med, sample.tfda, link.med, link.tfda)To assess the effectiveness of algorithms, the optimal solution and the optimal value of the objective function are read using the readsol.QAPLIB function:
url.sol <- "http://www.opt.math.tu-graz.ac.at/qaplib/soln.d/"
link.sol <- function(x) paste0(url.sol, x, ".sln")
sol.link <- lapply(sample, link.sol)
sol.opt <- lapply(sol.link, readsol.QAPLIB)
names(sol.opt) <- sampleWe will solve each instance using four methods:
The constructive heuristic for the QAP is implemented as follows:
This heuristic is implemented in the heuristic.QAP function, which returns the solution and objective function obtained with this heuristic, and a time variable equal to zero, since the time execution is negligible. The output is a sol.heuristic a list of 10 list containing the results of applying the constructive heuristic for each of the 10 instances.
solve.by.heuristic <- function(x){
flow <- x$flow
distance <- x$distance
sol.heuristic <- Heuristic.QAP(flow, distance)
return(list(obj = sol.heuristic$obj, sol=sol.heuristic$sol, time=0))
}
sol.heuristic <- lapply(data, solve.by.heuristic)We proceed to solve each instance through a simulated annealing algorithm. Results are stored in a sol.sa list, now including the time of execution:
solve.by.sa <- function(x){
flow <- x$flow
distance <- x$distance
starting <- Heuristic.QAP(flow, distance)
set.seed(1313)
time1 <- Sys.time()
sol.heuristic <- SimulatedAnnealing.QAP(flow, distance, 30000, starting$sol)
time2 <- Sys.time()
time <- time2 - time1
return(list(obj = sol.heuristic$obj, sol=sol.heuristic$sol, time=time))
return(sol.heuristic)
}
sol.sa <- lapply(data, solve.by.sa)The results of the tabu search are stored in the sol.ts list:
solve.by.ts <- function(x){
flow <- x$flow
distance <- x$distance
starting <- Heuristic.QAP(flow, distance)
set.seed(1313)
time1 <- Sys.time()
sol.heuristic <- TabuSearch.QAP(flow, distance, iter=30000, sol=starting$sol)
time2 <- Sys.time()
time <- time2 - time1
return(list(obj = sol.heuristic$obj, sol=sol.heuristic$sol, time=time))
return(sol.heuristic)
}
sol.ts <- lapply(data, solve.by.ts)And the results of the genetic algorithm are stored in a sol.ga list:
solve.by.ga <- function(x){
flow <- x$flow
distance <- x$distance
set.seed(1313)
time1 <- Sys.time()
sol.heuristic <- GeneticAlgorithm.QAP(flow, distance)
time2 <- Sys.time()
time <- time2 - time1
return(list(obj = sol.heuristic$obj, sol=sol.heuristic$sol, time=time))
return(sol.heuristic)
}
sol.ga <- lapply(data, solve.by.ga) Now we need to list the results for each instance. for each of the four resolution procedures (constructive heuristic, simulated annealing, tabu search and genetic algorithm) and for the optimal solution we report:
We will create a list of data frames called results with the above structure to report the results. First we define a SolString function which turns the solution of the QAP into a string:
SolString <- function(sol){
text <- character(0)
for (i in 1:length(sol)) text <- paste(text, sol[i])
text <- substring(text, 2)
return(text)
}Then we build the list results defining each of the columns of the data frame:
results <- list(0)
n <- length(sample)
for(i in 1:n){
results[[i]] <- data.frame(matrix(nrow=5, ncol=0))
results[[i]]$obj <- c(sol.heuristic[[i]]$obj, sol.sa[[i]]$obj, sol.ts[[i]]$obj, sol.ga[[i]]$obj, sol.opt[[i]]$obj)
results[[i]]$sol <- c(SolString(sol.heuristic[[i]]$sol), SolString(sol.sa[[i]]$sol), SolString(sol.ts[[i]]$sol), SolString(sol.ga[[i]]$sol), SolString(sol.opt[[i]]$sol))
results[[i]]$time <- c(sol.heuristic[[i]]$time, sol.sa[[i]]$time, sol.ts[[i]]$time, sol.ga[[i]]$time, sol.opt[[i]]$time)
results[[i]]$time <- round(results[[i]]$time, 2)
for(j in 1:5){
results[[i]]$eff[j] <- (results[[i]]$obj[j] - results[[i]]$obj[5])/results[[i]]$obj[5]
results[[i]]$eff[j] <- round(results[[i]]$eff[j], 2)
}
rownames(results[[i]]) <- c(paste("Heuristic", sample[[i]]), paste("Sim. Annealing", sample[[i]]), paste("Tabu", sample[[i]]), paste("Genetic", sample[[i]]), paste("Optimal", sample[[i]]))
}Then we can print the results:
library(stargazer)
for(i in 1:length(sample)) stargazer(results[[i]], type="text", summary=FALSE)##
## ====================================================================
## obj sol time eff
## --------------------------------------------------------------------
## Heuristic rou12 312,986 6 3 4 11 2 9 1 8 12 5 10 7 0 0.330
## Sim. Annealing rou12 257,372 4 5 7 11 2 3 6 10 1 8 12 9 1.240 0.090
## Tabu rou12 244,684 4 9 7 8 5 2 10 3 11 12 6 1 7.900 0.040
## Genetic rou12 252,974 10 7 8 9 12 6 4 2 1 5 3 11 23.730 0.070
## Optimal rou12 235,528 6 5 11 9 2 8 3 1 12 7 4 10 0 0
## --------------------------------------------------------------------
##
## =============================================================================
## obj sol time eff
## -----------------------------------------------------------------------------
## Heuristic rou15 447,162 6 4 13 11 5 9 1 8 15 7 10 2 14 3 12 0 0.260
## Sim. Annealing rou15 405,382 10 14 2 11 3 9 5 8 13 7 12 1 6 4 15 1.420 0.140
## Tabu rou15 375,754 12 7 1 13 14 6 10 11 4 2 3 5 15 9 8 11.330 0.060
## Genetic rou15 393,998 8 15 11 7 10 6 2 1 12 14 3 9 5 13 4 25.560 0.110
## Optimal rou15 354,210 12 6 8 13 5 3 15 2 7 1 9 10 4 14 11 0 0
## -----------------------------------------------------------------------------
##
## ============================================================================================
## obj sol time eff
## --------------------------------------------------------------------------------------------
## Heuristic rou20 904,310 6 5 20 17 8 9 16 7 1 15 3 12 13 4 18 11 10 14 2 19 0 0.250
## Sim. Annealing rou20 816,616 4 16 17 18 15 19 13 2 5 8 9 6 14 10 12 1 3 11 7 20 1.910 0.130
## Tabu rou20 779,782 3 6 17 7 5 2 15 12 18 8 9 1 19 14 16 11 20 10 4 13 24.560 0.070
## Genetic rou20 803,166 4 16 17 20 6 12 19 14 18 9 2 1 15 10 11 7 13 8 3 5 32.670 0.110
## Optimal rou20 725,522 1 19 2 14 10 16 11 20 9 5 7 4 8 18 15 3 12 17 13 6 0 0
## --------------------------------------------------------------------------------------------
##
## ===================================================================
## obj sol time eff
## -------------------------------------------------------------------
## Heuristic scr12 47,536 12 1 4 2 10 9 5 6 3 8 11 7 0 0.510
## Sim. Annealing scr12 35,576 8 7 6 11 5 2 10 9 1 4 12 3 1.340 0.130
## Tabu scr12 34,904 6 4 3 9 1 2 7 8 11 12 10 5 7.060 0.110
## Genetic scr12 35,158 1 11 5 9 10 3 2 4 12 8 7 6 23.780 0.120
## Optimal scr12 31,410 8 6 3 2 10 1 5 9 4 7 12 11 0 0
## -------------------------------------------------------------------
##
## =============================================================================
## obj sol time eff
## -----------------------------------------------------------------------------
## Heuristic scr15 117,726 14 1 7 2 13 9 5 6 3 8 15 12 10 4 11 0 1.300
## Sim. Annealing scr15 64,214 1 3 2 6 9 14 13 4 10 15 7 5 12 11 8 1.400 0.260
## Tabu scr15 56,698 8 7 2 4 5 12 10 6 11 15 14 9 1 13 3 12.040 0.110
## Genetic scr15 63,898 11 15 8 13 3 14 7 2 1 10 12 4 9 5 6 25.780 0.250
## Optimal scr15 51,140 15 7 11 8 1 4 3 2 12 6 13 5 14 10 9 0 0
## -----------------------------------------------------------------------------
##
## ============================================================================================
## obj sol time eff
## --------------------------------------------------------------------------------------------
## Heuristic scr20 232,046 18 6 4 7 17 14 5 1 20 12 13 11 15 8 16 9 10 19 3 2 0 1.110
## Sim. Annealing scr20 150,238 15 8 16 20 17 11 14 13 18 12 10 7 9 2 19 5 1 4 3 6 2.030 0.370
## Tabu scr20 128,434 7 2 18 9 6 4 3 14 20 19 12 10 8 1 17 15 5 13 16 11 22.730 0.170
## Genetic scr20 152,054 13 3 18 1 16 11 5 2 12 19 7 4 10 17 15 6 14 9 8 20 32.020 0.380
## Optimal scr20 110,030 20 7 12 6 4 8 3 2 14 11 18 9 19 15 16 17 13 5 10 1 0 0
## --------------------------------------------------------------------------------------------
##
## ==================================================================
## obj sol time eff
## ------------------------------------------------------------------
## Heuristic had12 1,920 6 1 10 4 9 2 3 12 5 7 8 11 0 0.160
## Sim. Annealing had12 1,676 8 10 2 11 5 12 7 3 6 1 4 9 1.180 0.010
## Tabu had12 1,668 3 10 11 2 6 7 12 5 8 1 9 4 6.250 0.010
## Genetic had12 1,684 8 10 12 11 2 6 7 5 3 1 9 4 24.160 0.020
## Optimal had12 1,652 3 10 11 2 12 5 6 7 8 1 4 9 0 0
## ------------------------------------------------------------------
##
## ==============================================================================
## obj sol time eff
## ------------------------------------------------------------------------------
## Heuristic had16 4,192 13 1 14 6 15 2 3 12 5 16 7 8 4 9 11 10 0 0.130
## Sim. Annealing had16 3,872 3 5 13 12 15 2 8 7 10 11 14 16 1 9 6 4 1.480 0.040
## Tabu had16 3,734 13 2 5 10 12 11 14 6 3 8 7 1 9 4 16 15 11.620 0
## Genetic had16 3,860 9 16 4 7 12 5 11 6 1 2 10 3 14 13 15 8 27.320 0.040
## Optimal had16 3,720 9 4 16 1 7 8 6 14 15 11 12 10 5 3 2 13 0 0
## ------------------------------------------------------------------------------
##
## ====================================================================================
## obj sol time eff
## ------------------------------------------------------------------------------------
## Heuristic had18 5,954 3 8 16 6 5 11 7 13 10 1 9 17 12 15 18 4 14 2 0 0.110
## Sim. Annealing had18 5,548 1 15 17 9 18 10 12 7 16 3 11 5 14 13 6 2 8 4 1.660 0.040
## Tabu had18 5,470 17 2 14 6 7 10 11 16 13 12 3 5 9 4 18 1 15 8 16.150 0.020
## Genetic had18 5,550 1 18 15 6 7 10 16 2 14 8 5 12 17 13 11 3 9 4 29.530 0.040
## Optimal had18 5,358 8 15 16 6 7 18 14 11 1 10 12 5 3 13 2 17 9 4 0 0
## ------------------------------------------------------------------------------------
##
## ==========================================================================================
## obj sol time eff
## ------------------------------------------------------------------------------------------
## Heuristic had20 7,902 3 11 16 17 9 8 10 14 19 1 6 4 12 7 13 18 20 2 5 15 0 0.140
## Sim. Annealing had20 7,290 1 4 19 18 11 10 5 7 16 12 3 2 8 20 13 14 15 9 6 17 1.870 0.050
## Tabu had20 7,270 8 9 16 11 10 5 3 14 4 12 19 1 17 20 7 6 15 13 18 2 21.700 0.050
## Genetic had20 7,180 8 19 16 6 7 20 18 10 4 11 12 5 2 13 14 17 15 9 1 3 32.310 0.040
## Optimal had20 6,922 8 15 16 14 19 6 7 17 1 12 10 11 5 20 2 3 4 9 18 13 0 0
## ------------------------------------------------------------------------------------------As can be seen from the results, the most effective heuristics are tabu search and genetic algorithm. In all instances except had20 tabu search beats simulated annealing, suggesting that perhaps for big instances genetic algorithm can have superior performance.