[eclipse-clp-users] Harder instances

Attached is a data file containing harder instances; this contains all the
instances off the Web site, plus the 1..13 instance I mentioned, and five
randomly generated instances for each power-of-two size from 1 up to 1024.

Also attached is my current solver code, which is based on a small
generalization of the Supowit algorithm (try the choices it makes first,
but backtrack over other choices if the height-12 rule forbids the choice
Supowit would make).

For all the cases in this data file, the attached code does one of two
things for me:

* Solves the problem to optimality in 0.0s as measured by the driver
* Generates exactly one solution in 0.2s or less, and then times out after
  a minute of trying to find a better solution.  (Testable by changing the
  marked comment lines near the top - use the call to build_stacks alone
  to return the first solution, or the call to bb_min to search for an
  optimal solution.)

This behaviour makes me suspect that in fact the first solution it finds
may always be optimal; but I don't have a proof of that.  Note, also, that
in the cases where it solves to optimality and does NOT time out, all
except number 40 (which is a handmade example) are because it produced a
height-limited solution matching the number of stacks in the
height-unlimited solution.  The instances on which the first solution is
worse than that, and then it times out looking for a better solution, are
numbers 83, and 86 through 95, in the attached data file.  I've attached
the output, too, showing the sizes of the solutions it found.
-- 
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