[R] Constrined dependent optimization.

[Hans W. Borchers]

Kevin,

sorry I don't understand this sentence:
"It has been suggested that I do a cluster analysis. Wouldn't this bet
mepart way there?"

Let your products be numbered  1, ..., n,  and let p(i) be the location
where product i is stored (assigned to) in the warehouse. Then p is a
permutation of the set  1, ..., n  and the task is an "assignment" problem.

A sale v is simply a subset of  1, ..., n and the contribution to the target
function could, for example, be

    f_v(p) = max( p(v) ) - min( p(v) )  for each sale v,

or whatever your evaluation criterion is. The total function to minimize
will then be  Sum( f_v)  for all historical sales v.

Because it is based on a distance, the whole task is called a "quadratic"
assignment problem (and is certainly not linear). 

In the literature you will find algorithms and tools mentioned to solve such
a task, and n = 20,000 is not that much nowadays. But the difference between 
n = 100  and  n = 20,000  is huge for tools not specialized to the task.

For the TSP, imagine two groups of cities very far apart. Then under some
mild restrictions it would not be reasonable to go back and forth between
these groups several times, and therefore the problem could be split into
two independent subproblems.

So the question of clustering belongs to the data preparation part.

Whether such really different classes of sales exist in your data, only you
can decide. In my experience, most of the time such preprocessing is not
worth doing and will not speed up the optimization procedure considerably.

Regards,  Hans Werner



rkevinburton wrote:
> 
> 
> It has been suggested that I do a cluster analysis. Wouldn't this bet
> mepart way there?
> 
> Thank you for your response I am looking up the book now.
> 
> Kevin
> 
> ---- "Hans W. Borchers" <hwborchers at googlemail.com> wrote:
>>
>> Just in case you are still interested in theoretical aspects:
>>
>> In combinatorial optimization, the problem you describe is known as the
>> Quadratic (Sum) Assignment Problem (QAP or QSAP) and is well known to
>> arise in facility and warehouse layouts. The task itself is considered
>> hard, comparable to the Traveling Salesman Problem (TSP).
>>
>> I would clearly advise to turn to some specialized commercial software
>> for solving it, otherwise you will very likely get stuck in suboptimal
>> solutions miles away from the true optimum. And for a real commercial
>> situation this may be disastrous.
>>
>> Regards,  Hans Werner
>>
>> P.S.:   See for instance Cela: The Quadratic Assignment Problem. Theory
>> and Algorithms, Springer, 2000.  (Partly available at books.google.com)
>>
> 
> 

-- 
View this message in context: http://www.nabble.com/Constrined-dependent-optimization.-tp22772520p22966416.html
Sent from the R help mailing list archive at Nabble.com.