Comparing localsolver with Rglpk on k-medoids example
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.
Recently I have coauthored a new localsolver package that can be used to solve large scale optimization problems from R. It is a wrapper around commercial solver that is free for academia. If you are interested why it is worthwhile to give it a look – read on.
Before we begin
The test problem
Let us start with code that generates test matrices for our examples:
kmedoids.generate.data <- function(seed, N, P) {
if(!is.null(seed)) {
set.seed(seed)
}
InfiniteDist <- 10000.0
Dist <- matrix(round(runif(n=N * N) * 100, digits = 0),
nrow = N)
diag(Dist) <- 0
return(list(
N = as.integer(N),
P = as.integer(P),
Dist = Dist,
InfiniteDist = InfiniteDist))
}
data <- kmedoids.generate.data(seed = 1234, N = 20L, P = 5L)
One thing that is worth explaining is that in the code we define InfiniteDist which will serve us as surrogate for infinity (all actual distances are shorter than it).
Now let me present how the problem can be solved with localsolver and Rglpk.
localsolver approach
library(localsolver)
lsp.model <- "function model() {
x[1..N] <- bool() ; // point i is in P iff x[i] = 1
constraint sum[i in 1..N](x[i]) == P ;
minDist[i in 1..N] <- min[j in 1..N](
x[j] ? Dist[j][i] : InfiniteDist);
// minimize sum of distances
objective <- sum[i in 1..N]( minDist[i] ) ;
minimize objective;
}”
lsp <- ls.problem(model.text.lsp = lsp.model)
lsp <- set.params(lsp = lsp, lsTimeLimit = 1)
lsp <- set.params(lsp = lsp, lsNbThreads = 1)
lsp <- add.output.expr(lsp=lsp, expr.text.lsp = "x",
dimensions = data$N)
lsp <- add.output.expr(lsp=lsp, expr.text.lsp = "objective",
dimensions = 1)
lsp.solution <- ls.solve(lsp = lsp, data = data)
Notice that we can define the optimization problem using a simple domain specific language as a string. Interestingly in the string we can use all variables defined in data list as localsolver is able to interact with extrernal data source. Additionally using set.params and add.output.expr we can set up the parameters of optimization engine and optimization output we will want to collect.
As a result we get a list with optimization output. Importantly the contents of the list can be controlled programatically as mentioned above.
Rglpk approach
In my opinion the code looks cryptic in comparison to localsolver specification. There are two reasons for such a situation:
- we have to have two mix two types of decision variables: location of depots and assignment of locations to depots
- we have to construct a complex constraints matrix combining different types of conditions in one big data structure
Summary
- using natural (mathematical) formulation of objective function and constraints
- allowing to dynamically update reference data: that lsp.model string did not have any hard coded constants – everything is loaded from metadata provided as R list.
R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.