[cadynce] How Many Configurations Is Enough?

[Gautam Thaker]

Raj Rajkumar wrote:
> Dear Joe, Gautam and Patrick:
> 
> On a somewhat different note, the current configuration generator uses 
> single-dimensional bin-packing.   ARMS-2 results indicated that 
> relatively simple multi-dimensional variants of classical heuristics 
> tend to work pretty well.   At CMU, a small group of us (including a 
> former PhD student of mine named Dr. Dio DeNiz who is now at the SEI) 
> has been spending some time reading and studying the worst-case 
> behaviors of multi-dimensional bin-packing. 
> There are some surprising (i.e. negative) performance bounds out there 
> on multi-dimensional bin-packing.   Briefly, if we have k dimensions, a 
> polynomial-time heuristic may require as many (k+1) times as many 
> processors as required by the optimal packing.   The lower bound is 150% 
> (i.e. 50% more processors than the optimal).    Initially, we thought 
> that the upper bound was perhaps pessimistic, but after playing around 
> with some numbers, we found one case with k=3 dimensions, the optimal 
> requires two bins while a fairly smart heuristic (the one that Gaurav 
> used in ARMS-2) required 4 processors.  In other words, we required 
> (k-1) times more processors than the optimal.   Please note that these 
> are worst-case (pathological) scenarios.   We continue to believe that 
> in practice, multi-dimensional packing heuristics will do well in 
> general and an ensemble will do incredibly better.  For example, for the 
> above case, WFD solved it quickly to get the optimal! It may stumble on 
> other cases however - encouraging the use of ensembles.
> 
> Two takeaways:
> 
> 1. With multi-dimensional bin-packing, there may be scenarios where the 
> number of processors required can be significantly higher than what one 
> might have come to expect.
> 2. An ensemble of multi-dimensional bin-packing heuristics will do well.

Hi Raj:

When I met with Carol Galloway and others at NSWC Dahlgren on May 2nd 
one of the points Paul Werme asked me about was this exact issues. He 
worried that PoR may have as many as 10 dimensions to pack and he 
worried if that presented problems to allocators. I had replied that 
more the dimensions more difficult things will be but that I will 
discuss this point within the cadynce community. Glad this has come up. 
I had also said that this being "Box 2", meaning off line analysis, we 
did not mind spending lots of CPU time to generate candidate allocations.

I think we can address this point in coming weeks but nothing much can 
be done this week. Perhaps we can talk about this in depth if and when 
we convene the cadynce team for the next face to face meeting. I remain 
of hope that for most practical cases we can find solutions given that 
this is offline (box 2).

Gautam

> 
> ---
> Raj
> 
> _______________________________________________
> Cadynce mailing list
> Cadynce at list.isis.vanderbilt.edu
> http://list.isis.vanderbilt.edu/mailman/listinfo/cadynce