[eclipse-clp-users] Harder instances

From: Matthew Skala <mskala_at_cs.toronto.edu>
Date: Mon, 22 Mar 2010 16:59:19 -0400 (EDT)
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

Received on Mon Mar 22 2010 - 20:56:23 CET

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