[R] Constrined dependent optimization.

[Ben Bolker]

  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>