[R] Constrined dependent optimization.

[Paul Smith]

As I told you before, without knowing the definition of your function
f, one cannot help much.

Paul


On Wed, Apr 1, 2009 at 3:15 PM,  <rkevinburton at charter.net> wrote:
> Thank you I had not considered using "gradient" in this fashion. Now as an add on question. You (an others) have suggested using SANN. Does your answer change if instead of 100 "variables" or bins there are 20,000? From the documentation L-BFGS-B is designed for a large number of variables. But maybe SANN can handle this as well.
>
> 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.
>
>