How to use "sann" function in R to solve graph problems?

Question

I came across a package in R which has a function called sann for simulated annealing.

sann uses parameters fn and gr to optimize and to select new points, respectively.

For something like the max-clique or max-stable set problems, fn would be a summing function, but it's less clear how one would formulate gr to fix these graph computations. In these cases, how would gr "select"?

Answer 1

First, some clarification on terminology.

A package in R is a collection of R functions, data, and compiled code in a well-defined format.

SANN (sann) is not a package. Depending on which package you're using, sann is either a function or, more often, a method used within an optimization function.

Packages containing sann include optim, trustOptim, consPlan, and constrOptim.

In the package optim, the sann method is implemented as:

> func <- function(x){
+   out <- (x[1]-2)^2 + (x[2]-1)^2
+   return <- out
+   }> 
> optim(par=c(0,0), fn=func, gr = NULL,
+       method = c("SANN"),
+       lower = -Inf, upper = Inf,
+       control = list(), hessian = T)

As you said, for the "SANN" (sann) method gr is used to generate a new candidate point. If it is NULL a default Gaussian Markov kernel is used.

Now in your use case -- the case of a graph -- what you probably want to do is to use par and value to pass values to fn and gr. This is a nice feature of this implementation of SANN in optim which is covered a little more than half way through this documentation page.

par is the best set of parameters found and value is the value of fn corresponding to par.