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, <rkevinbur...@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 <phh...@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 <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.
>
>
______________________________________________
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.
