From: Sergii Dymchenko <kit1980_at_gmail.com>

Date: Tue, 2 Jul 2013 23:55:10 -0700

Date: Tue, 2 Jul 2013 23:55:10 -0700

Thanks for suggestions, About gfd. As Kish pointed to, changing cloning_distance made a world of difference regarding memory usage. I tried changing it from default 2 to 100 and 1000 and was able to solve queens up to 10 thousand. For example, N = 4000 with cloning_distance = 100 take less than 2 minutes on my laptop, but unfortunately it scales badly after 10000 or so. Strangely, doing search inside Gecode (with gfd:search(Qs, 0, most_constrained, indomain_median, complete, []) ) eats memory very fast compared to gfd_search:search(Qs, 0, most_constrained, indomain_median, complete, []) with large cloning_distance. I plan to do the same program in Gecode C++ directly and look at the speed and memory consumption. Also I've implemented simulated annealing using 'tentative' and 'tentative_constraints' libraries pointed to by Joachim (I didn't really look at 'repair' library because 'tentative' "is intended as a successor for library(repair)."). After some tweaking N = 4000 took 1m15s on my laptop, and N = 33000 took about 2.5 hours (which is acceptable) with very little memory consumption. I reimplemented the same simulated annealing algorithm in C++ from scratch and got about 8 seconds for N = 4000 and about 12 minutes for N = 33000. Sergii. On Tue, Jul 2, 2013 at 7:18 AM, Joachim Schimpf <jschimpf_at_coninfer.com>wrote: > On 29/06/2013 16:04, Helmut Simonis wrote: > > For large n-queens problems, a repair based method typically works very > > well. I seem to recall a library in ECLiPSe for this. > > > > Regards > > > > Helmut > > > >> Hi, > >> > >> In the online course https://class.coursera.org/optimization-001 I > have an > >> assignment to solve N-Queens problem of the size as large as possible. > >> > >> For now the max size I've solved is N=4000. To get maximum grade for the > >> problem N ~ 30000 is needed. > > You can find Local Search based code for queens in the example for > library(tentative): > http://www.eclipseclp.org/doc/bips/lib/tentative_constraints/index.html > > This works well for a few thousand queens, and 10000 take a few minutes > to solve, without any memory problems. To do 30000 in a reasonable time, > it may need some work on the (rather naive) heuristic. Let us know if > you manage to improve it! > > Cheers, > Joachim > > > > > > > ------------------------------------------------------------------------------ > This SF.net email is sponsored by Windows: > > Build for Windows Store. > > http://p.sf.net/sfu/windows-dev2dev > _______________________________________________ > ECLiPSe-CLP-Users mailing list > ECLiPSe-CLP-Users_at_lists.sourceforge.net > https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users >Received on Wed Jul 03 2013 - 06:55:18 CEST

*
This archive was generated by hypermail 2.2.0
: Fri Jul 05 2013 - 18:13:15 CEST
*