[cadynce] How Many Configurations Is Enough?

[Cross, Joseph]

Raj -

These are very interesting results. I guess we've all done so much
single-dimensional packing that the pathologies there now seem normal,
so it's good to get some nice, fresh, pathologies to contemplate.

I've heard dark mutterings that PoR really needs like 7 dimensional bin
packing. Does anybody know what those 7 dimensions are? Is someone
perhaps counting constraints like security class as dimensions? We
should find out ASAP how deep our (fresh, new) kimchi is.

- Joe

> -----Original Message-----
> From: Raj Rajkumar [mailto:raj at ece.cmu.edu] 
> Sent: Tuesday, May 22, 2007 6:55 PM
> To: Cross, Joseph
> Cc: cadynce at list.isis.vanderbilt.edu
> Subject: Re: [cadynce] How Many Configurations Is Enough?
> 
> 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
> 
>