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 ... rkevinbur...@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 <bol...@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@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 bol...@ufl.edu / www.zoology.ufl.edu/bolker GPG key: www.zoology.ufl.edu/bolker/benbolker-publickey.asc
signature.asc
Description: OpenPGP digital signature
______________________________________________ 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.
