From: Joachim Schimpf <joachim.schimpf_at_infotech.monash.edu.au>

Date: Sun, 21 Mar 2010 23:57:51 +1100

Date: Sun, 21 Mar 2010 23:57:51 +1100

I have set up a page on the web site to turn this into a little programming competition: http://eclipse-clp.org/examples/challenge.html The deadline is in 3 weeks, lets see how good we can get! Benoit's solution solves 12 of the 40 problem instances within a minute, but times out for the others. The largest problem it solves has 15 boxes, so there is plenty of room for improvement: different models, other constraints, other solvers, heuristics, maybe there is even an efficient algorithm for the problem? Riyadh's solution looks correct, but is a generate-and-test approach. This can only work for very small instances or lucky data sets like the one he used. A list of length N has N! permutations, or 265252859812191058636308480000000 for N=30, which is about the age of the universe in femtoseconds. What a constraint programming solution does is to use the constraints to cut the search space to a manageable size. Good luck ;-) JoachimReceived on Sun Mar 21 2010 - 12:58:01 CET

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