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? Kevin
rkevinburton 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? > >See method "SANN" under ?optim. Ben Bolker -- View this message in context: http://www.nabble.com/Constrined-dependent-optimization.-tp22772520p22772795.html Sent from the R help mailing list archive at Nabble.com.
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
rkevinburton at charter.net wrote:> I am sorry but I don't see the connection. with SANN and say 3 > variables one of the steps may increment x[1] by 0.1. Not only is > this a non-discrete integer value but even if I could coerce SANN to > only return discrete integer values for each step in the optimization > once x[1] was set to say 2 I would have to search the other > "variables" for a value of 2 and exchange x[1] and which ever > variable was two so as to maintain the property that each variable > has a unique discrete value constained from 1 : number of varables. > > Thank you. > > KevinIf you look more closely at the docs for method="SANN" (and the examples), you'll see that SANN allows you to pass the "gradient" argument (gr) as a custom function to provide the candidate distribution. Here's an example: N <- 10 xvec <- seq(0,1,length=N) target <- rank((xvec-0.2)^2) objfun <- function(x) { sum((x-target)^2)/1e6 } objfun(1:100) swapfun <- function(x,N=10) { loc <- sample(N,size=2,replace=FALSE) tmp <- x[loc[1]] x[loc[1]] <- x[loc[2]] x[loc[2]] <- tmp x } set.seed(1001) opt1 <- optim(fn=objfun, par=1:N, gr=swapfun,method="SANN", control=list(trace=10)) plot(opt1$par,target)> ---- Ben Bolker <bolker at ufl.edu> wrote: >> >> >> rkevinburton 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? >>> >>> >> See method "SANN" under ?optim. >> >> Ben Bolker >> >> -- View this message in context: >> http://www.nabble.com/Constrined-dependent-optimization.-tp22772520p22772795.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. >-- Ben Bolker Associate professor, Biology Dep't, Univ. of Florida bolker at ufl.edu / www.zoology.ufl.edu/bolker GPG key: www.zoology.ufl.edu/bolker/benbolker-publickey.asc -------------- next part -------------- A non-text attachment was scrubbed... Name: signature.asc Type: application/pgp-signature Size: 260 bytes Desc: OpenPGP digital signature URL: <https://stat.ethz.ch/pipermail/r-help/attachments/20090330/ab2f6fd3/attachment-0003.bin>
Just a quick thought: if you have the locations of the items along a line segment (the "warehouse"), can you find a way to formulate the problem so that the average distances represent a matrix calculation (i.e., multiply some huge matrix by the locations) then it's a linear problem ... It's too bad there aren't more operations researchers on this list -- I'm sure they do this sort of thing all the time ... rkevinburton at charter.net wrote:> Thank you for the suggestion but I am not sure how to formulate the > problem in linear programming terms. Stated very simply the problem > is a warehouse problem. We are trying to place the items in an > optimal position so as to minimize the distance needed to travel to > pick the items to fulfill an order. For example an order would come > in for A, B, C. In the worst case A would be on one end of the > warehouse, B in the middle and C on the other end. The ideal case > would be that A, B, and C are within close proximity. So the > variables are the positions of the items in the warehouse. The > distance function would be the distance from A to B plus the distance > from B to C (assuming the absolute locations are sorted). The > function that I would like to minimize would be average distance for > all orders over say the last month. So the large number of variables > is due to the large number of items and positions in the warehouse. > So having explained myself a little better does it still sound to you > like a linear programming problem? I am having a hard time thinking > of it in those terms. > > Thanks again. > > Kevin > > ---- Ben Bolker <bolker at ufl.edu> wrote: >> >> >> rkevinburton 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 >>> >> It's a question of time and space. Try the problem for 100, 500, >> 1000 ... variables to see how the memory usage and time scale. (At >> a guess, memory will be linear in N and not too bad, time will be >> horrible.) I haven't followed the thread very carefully, if any of >> the linear programming solutions solve your problem they will be >> far more efficient. It sounds as though you have an extremely >> non-trivial optimization problem here, the brute-force approach >> exemplified by SANN may not work, so you will have to map your >> problem onto a framework (such as linear programming) that strives >> for efficiency rather than generality. (L-BFGS-B is out of the >> question.) >> >> Essentially, this is turning into an optimization problem rather >> than an R problem. Once you know that there exists an optimization >> approach that can solve your problem before the sun burns out, you >> can come back and find out if anyone has implemented it in R (or >> RSiteSearch() for it ...), or implemented an interface with a >> lower-level platform. >> >> Good luck, Ben Bolker -- View this message in context: >> http://www.nabble.com/Constrined-dependent-optimization.-tp22772520p22834746.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. >-- Ben Bolker Associate professor, Biology Dep't, Univ. of Florida bolker at ufl.edu / www.zoology.ufl.edu/bolker GPG key: www.zoology.ufl.edu/bolker/benbolker-publickey.asc -------------- next part -------------- A non-text attachment was scrubbed... Name: signature.asc Type: application/pgp-signature Size: 260 bytes Desc: OpenPGP digital signature URL: <https://stat.ethz.ch/pipermail/r-help/attachments/20090402/5383ee72/attachment-0002.bin>