# [R] Combinatorial Optimisation

ripley@stats.ox.ac.uk ripley@stats.ox.ac.uk
Fri, 25 Oct 2002 13:01:43 +0100 (BST)

```Adrian,

Thanks for the idea.  If you were willing to contribute a patch to do this
we would be happy to incorporate it.

Brian

On Fri, 25 Oct 2002, Adrian Trapletti wrote:

> > Date: Thu, 24 Oct 2002 08:58:08 +0200 (CEST)
> > From: Detlef Steuer <Detlef.Steuer@unibw-hamburg.de>
> > Subject: RE: [R] Combinatorial Optimisation
> >
> > This thread missed me somehow.
> >
> > If not mentioned before:
> > simulated annealing is implemented in optim().
>
> The current implementation of simulated annealing in optim() has been designed for a continuos parameter space. The next candidate
> point in the parameter space is generated from a Gaussian Markov kernel with scale proportional to the actual temperature. However,
> it is quite simple to change this for a combinatorial optimization:
>
> in the R source tree, see the file src/main/optim.c, function samin:
>
> What you need to change are the four lines, that are responsible for generating a new candidate point:
>
> for (i = 0; i < n; i++)
>   dp[i] = scale * t * norm_rand();  /* random perturbation */
> for (i = 0; i < n; i++)
>   ptry[i] = p[i] + dp[i];  /* new candidate point */
>
> You could, e.g., replace them by a call to an R function, which randomly selects a new candidate point of a finite set of points.
> Hence, to quickly get SA for combinatorial optimization:

(Using an R function here is not entirely trivial, hence the request
above.)

> Copy and paste samin from optim.c
> Change the four lines
> Write an R wrapper for this new function
>
> best
>
> PS: TO R-DEVEL: What about having this behaviour in optim (default as is, optional a function argument which selects a candidate
> point)?
>
> --
> Dr. Adrian Trapletti             Phone :             +41 (0) 1 994 5631
> Trapletti Statistical Computing  Mobile:             +41 (0)76 370 5631
> Wildsbergstrasse 31              Fax   :             +41 (0) 1 994 5631
> CH-8610 Uster                    Email :  mailto:a.trapletti@bluewin.ch
> Switzerland                      WWW   : http://trapletti.homelinux.com
>
>
>
> -.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-
> r-help mailing list -- Read http://www.ci.tuwien.ac.at/~hornik/R/R-FAQ.html
> Send "info", "help", or "[un]subscribe"
> (in the "body", not the subject !)  To: r-help-request@stat.math.ethz.ch
> _._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._
>

--
Brian D. Ripley,                  ripley@stats.ox.ac.uk
Professor of Applied Statistics,  http://www.stats.ox.ac.uk/~ripley/
University of Oxford,             Tel:  +44 1865 272861 (self)
1 South Parks Road,                     +44 1865 272860 (secr)
Oxford OX1 3TG, UK                Fax:  +44 1865 272595

-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-
r-devel mailing list -- Read http://www.ci.tuwien.ac.at/~hornik/R/R-FAQ.html
Send "info", "help", or "[un]subscribe"
(in the "body", not the subject !)  To: r-devel-request@stat.math.ethz.ch
_._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._

```