Re: [eclipse-clp-users] Programming challenge (Re: constraint on indexed elements)

From: Joachim Schimpf <joachim.schimpf_at_infotech.monash.edu.au>
Date: Mon, 22 Mar 2010 10:37:58 +1100
Matthew Skala wrote:
> 
> Can there be duplicate boxes, and if so can a box be placed on top of
> an identical box?
> 
> I think that the problem as stated excludes duplicate boxes because it
> says "different sizes"; and the use of "greater than or equal" in the
> rules for stacking seems to suggest that if there were two identical
> boxes, then one could stack on top of the other.

I think we'll interpret "different" here as "various", and allow
duplicates (although the data set doesn't contain any).

Stacking identical boxes on top of each other is definitely allowed.
Thorsten Winterer wrote:


> In either of those cases
> (no duplicates, or duplicates may be placed on each other) then *except
> for the restriction of 12 boxes per stack*, this is the minimal chain
> decomposition problem, for which an efficient algorithm is given in the
> paper below.

Thanks for this hint!


Thorsten Winterer wrote:
>
> (By the way, if I read it correctly, then Benoit's program has an
> additional constraint on the maximum stack height, namely that
> Height =< integer(ceiling(NumBoxes/NumStacks)). This makes the problem harder!)

Yes, I'm a bit puzzled by that, maybe Benoit can explain.
It was not in the problem statement, maybe it is meant as
a heuristic in his program?


-- Joachim
Received on Sun Mar 21 2010 - 23:36:48 CET

This archive was generated by hypermail 2.2.0 : Thu Feb 02 2012 - 02:31:58 CET