[cadynce] How Many Configurations Is Enough?

[Raj Rajkumar]

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.

---
Raj