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

Hi,

with the attached program (which I started writing by re-using Benoit's program, although only a few bits are left), I get solutions for 29 instances within one minute, although some instances have not been proven optimal:
(By the way, if I read it correctly, then Benoit's program has an additional constraint on the maximum stack height, namely that Height =< integer(ceiling(NumBoxes/NumStacks)). This makes the problem harder!)

The program found the following solutions (given as number of stacks):

with choice = indomain_min

Set   Best solution
-----------------------
0     4 stacks
1     3
2     3
3     4
4     4
5     4
6     3
7     3
8     5*
9     6*
10    5* 
11    4*
12    4
13    5*
16    6*
17    7*
18    4
19    3
20    5*
21    5*
22    7*
23    4*
26    5*
27    6*
30    6*
31    8*
38    5*

with choice = indomain_random, two more could be solved:

14    6* stacks
36    7*


Solutions marked with * are not proven optimal.

Using indomain_max as choice method produces solutions for the remaining data sets, but they were of course far from optimal.

I think that with better variable selection and value choice methods, there could still be some improvements.

As a first try, I changed the program to fill the stacks diagonally, i.e., first the bottom slot of the left most stack, then the one above, then the bottom slot of the second stack, then the third one in the first, etc. 
I haven't attached this variant, since the code is rather crude (even compared to the attached program!), but I got the following additional solutions:

14    5* stacks (improved upon the solution mentioned above)
15    5*
29    6*
32    6*
33    7*
36    6* (improved upon the solution mentioned above)
37    5*
39    9*


Switching from complete search to LDS(2) gained more solutions:

24    6* stacks
25    6*
35    8*


For data sets 28 and 34, I changed the variable selection again: first fill the bottom row, then the next row, etc. Search method is again LDS(2), and optimization method for branch-and-bound is dichotomic. With these settings, I get the following solutions:

28   14* stacks
34   19*

Both solutions can be improved manually rather easily, so LDS(2) is too restrictive, which means that the variable and value selection strategies are still sub-optimal.


I haven't attached any of the solutions, but can provide them on request.

Cheers,
Thorsten