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
This archive was generated by hypermail 2.2.0 : Thu Feb 02 2012 - 02:31:58 CET