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

From: Matthew Skala <mskala_at_cs.toronto.edu>
Date: Mon, 22 Mar 2010 12:23:25 -0400 (EDT)
On Mon, 22 Mar 2010, Thorsten Winterer wrote:
> If the stack height is simply restricted to be at most 12 boxes, then I can
> remove the stack height constraints from my program and add a symmetry
> breaking constraint that orders the box class indexes in the bottom row and
> get the following results:

I think we need much harder instances for testing.  The attached code
implements Supowit's algorithm from the paper I cited.  If this code
produces a solution with 12 or fewer blocks per stack, then that solution
is optimal; and even if not, the number of stacks it produces must be a
lower bound on the correct number.  I had intended to use it as a
quick-reject to find just the instances that needed a smarter search, and
to set the initial bounds for the objective variable; but it turns out
that it solves all the test instances to optimality.

This code gives the same number-of-stacks results as Thorstein's code;
however, it does every instance in 0.0s on my computer.  This code does
*not* enforce the stack-height limitation; if you give it an instance
which can be solved with fewer stacks by ignoring that limitation, it will
fail with the driver program reporting "bug."  One example of such an
instance is the one that goes [box(1,1),box(2,2),...,box(13,13)].
However, none of the test instances have that property.

By the way, the driver doesn't seem to do the right thing if stack/2 fails
in the ordinary Prolog way of failing, as opposed to returning but with an
incorrect answer.  I had to add an extra clause to make it return a bogus
solution so the driver would complain when the solver failed.
-- 
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 - 16:20:38 CET

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