Apparently, the convergence is faster if one uses this new swap function: swapfun <- function(x,N=100) { loc <- c(sample(1:(N/2),size=1,replace=FALSE),sample((N/2):100,1)) tmp <- x[loc[1]] x[loc[1]] <- x[loc[2]] x[loc[2]] <- tmp x }
It seems that within 20 millions of iterations, one gets the exact optimal solution, which does not take too long. Paul On Mon, Mar 30, 2009 at 5:11 PM, Paul Smith <phh...@gmail.com> wrote: > Optim with SANN also solves your example: > > ------------------------------------------- > > f <- function(x) sum(c(1:50,50:1)*x) > > swapfun <- function(x,N=100) { > loc <- sample(N,size=2,replace=FALSE) > tmp <- x[loc[1]] > x[loc[1]] <- x[loc[2]] > x[loc[2]] <- tmp > x > } > > N <- 100 > > opt1 <- > optim(fn=f,par=sample(1:N,N),gr=swapfun,method="SANN",control=list(maxit=50000,fnscale=-1,trace=10)) > opt1$par > opt1$value > > ------------------------------------------- > > We need to specify a large number of iterations to get the optimal > solution. The objective function at the optimum is 170425, and one > gets a close value with optim and SANN. > > Paul > > > On Mon, Mar 30, 2009 at 2:22 PM, Hans W. Borchers > <hwborch...@googlemail.com> wrote: >> >> Image you want to minimize the following linear function >> >> f <- function(x) sum( c(1:50, 50:1) * x / (50*51) ) >> >> on the set of all permutations of the numbers 1,..., 100. >> >> I wonder how will you do that with lpSolve? I would simply order >> the coefficients and then sort the numbers 1,...,100 accordingly. >> >> I am also wondering how optim with "SANN" could be applied here. >> >> As this is a problem in the area of discrete optimization resp. >> constraint programming, I propose to use an appropriate program >> here such as the free software Bprolog. I would be interested to >> learn what others propose. >> >> Of course, if we don't know anything about the function f then >> it amounts to an exhaustive search on the 100! permutations -- >> probably not a feasible job. >> >> Regards, Hans Werner >> >> >> >> Paul Smith wrote: >>> >>> On Sun, Mar 29, 2009 at 9:45 PM, <rkevinbur...@charter.net> wrote: >>>> I have an optimization question that I was hoping to get some suggestions >>>> on how best to go about sovling it. I would think there is probably a >>>> package that addresses this problem. >>>> >>>> This is an ordering optimzation problem. Best to describe it with a >>>> simple example. Say I have 100 "bins" each with a ball in it numbered >>>> from 1 to 100. Each bin can only hold one ball. This optimization is that >>>> I have a function 'f' that this array of bins and returns a number. The >>>> number returned from f(1,2,3,4....) would return a different number from >>>> that of f(2,1,3,4....). The optimization is finding the optimum order of >>>> these balls so as to produce a minimum value from 'f'.I cannot use the >>>> regular 'optim' algorithms because a) the values are discrete, and b) the >>>> values are dependent ie. when the "variable" representing the bin >>>> location is changed (in this example a new ball is put there) the >>>> existing ball will need to be moved to another bin (probably swapping >>>> positions), and c) each "variable" is constrained, in the example above >>>> the only allowable values are integers from 1-100. So the problem becomes >>>> finding the optimum order of the "balls". >>>> >>>> Any suggestions? >>> >>> If your function f is linear, then you can use lpSolve. >>> >>> Paul >>> >>> ______________________________________________ >>> R-help@r-project.org mailing list >>> https://stat.ethz.ch/mailman/listinfo/r-help >>> PLEASE do read the posting guide >>> http://www.R-project.org/posting-guide.html >>> and provide commented, minimal, self-contained, reproducible code. >>> >>> >> >> -- >> View this message in context: >> http://www.nabble.com/Constrined-dependent-optimization.-tp22772520p22782922.html >> Sent from the R help mailing list archive at Nabble.com. >> >> ______________________________________________ >> R-help@r-project.org mailing list >> https://stat.ethz.ch/mailman/listinfo/r-help >> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html >> and provide commented, minimal, self-contained, reproducible code. >> > ______________________________________________ R-help@r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.