[R] Constrined dependent optimization.

[rkevinburton at charter.net]

I have decided to use this SANN approach to my problem but to keep the run time reasonable instead of 20,000 variables I will randomly sample this space to get the number of variables under 100. But I want to do this a number of times. Is there someone who could help me set up WINBUGS to repeat this optimization N times each time randomly picking 100 of the possible 20,000.

Comments?

Kevin

---- Paul Smith <phhs80 at gmail.com> wrote: 
> 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 <phhs80 at 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
> > <hwborchers at 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,  <rkevinburton at 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 at 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 at 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 at 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.