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

On Sun, 21 Mar 2010, Joachim Schimpf wrote:
> problem it solves has 15 boxes, so there is plenty of room
> for improvement: different models, other constraints, other
> solvers, heuristics, maybe there is even an efficient
> algorithm for the problem?

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.  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.  A group I work with at the University of Waterloo recently
published a paper that I presented at ISAAC'09 (and even more recently, we
submitted the journal version) and that drew heavily on the Supowit paper,
so it's fresh in my mind.

@article{Supowit:Decomposing,
  author    = "Kenneth J. Supowit",
  title     = "Decomposing a Set of Points into Chains, with Applications
               to Permutation and Circle Graphs",
  journal   = "Information Processing Letters",
  volume    = "21",
  number    = "5",
  year      = "1985",
  pages     = "249--252",
  bibsource = "DBLP, http://dblp.uni-trier.de",
}

I don't know what the consequences of the limit on total chain length may
be.  Nonetheless, the Supowit algorithm might provide a good starting
point for clever heuristics.  At the very least, if you run the Supowit
algorithm and the result happens to have all chains of length 12 or less,
then you know you're done.  If people need help obtaining the Supowit
paper, they should contact me off-list.

(Why reveal this information to possible "opponents"?  It'll make for a
more interesting race if we all run from the same starting line!)
-- 
Matthew Skala, postdoctoral researcher, Universities of Toronto and Waterloo
mskala_at_cs.toronto.edu    mskala_at_cs.uwaterloo.ca    mskala_at_ansuz.sooke.bc.ca