[R] Constrined dependent optimization.

Paul Smith phhs80 at gmail.com
Thu Apr 2 18:23:10 CEST 2009


On Thu, Apr 2, 2009 at 3:49 PM,  <rkevinburton at charter.net> wrote:
> 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?


>From the description of your problem and as far as I understand it, it
seems that the problem is linear. Integer programming is typically
slow when the number of variables is high, and I do not know any
large-scale integer program solver. However, you may try continuous
linear programming (which is generally fast) to solve your integer
programming problem as a continuous linear program, rounding the
optimal solution at the end. Of course, with this technique there is
no guarantee of obtaining an optimal solution, but you may get a
solution close to the optimal one.

Paul




More information about the R-help mailing list