Sorry I sent a description of the function I was trying to minimize but I must 
not have sent it to this group (and you). Hopefully with this clearer 
description of my problem you might have some suggestions. 

It is basically a warehouse placement problem. You have a warehouse that has 
many items each placed in a certain bin (the "real" warehouse has about 20,000 
of these bins, hence the large number of variables that I want to input to 
optimize). Now assume that an order comes in for three items A, B, and C. In 
the worst case A will be on one end of the warehouse, B in the middle and C on 
the other end of the warehouse. The "work" involved in getting these items to 
fulfill this order is roughly proportional to the distance from A to B plus the 
distance from B to C (assuming the absolute positions are sorted). So the cost 
for fulfilling this order is this distance. In the ideal world A, B, and C 
would be right next to each other and the cost/distance would be minimized. So 
the function I want to minimize would be placing these 20,000 items in such a 
way so that the minimum "work" is involved in fulfilling the orders for the 
past month or two. Clearer? 

I can see that I may need to cut back on the variables 20,000 is probably too 
many. Maybe I can take the top 1,000 or so. I just am not sure of the packages 
available what to reasonably expect. I would like this optimization to complete 
in a reasonable amount of time (less than a few days). I have heard that SANN 
is slower than other optimization methods but it does have the feature of 
supplying a "gradient" as you pointed out. Are there other packages out there 
that might be better suited to such a large scale optimizaiton?

Thanks again.

Kevin
---- Paul Smith <phh...@gmail.com> wrote: 
> 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.

______________________________________________
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.

Reply via email to