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.