Re: [eclipse-clp-users] Symmetry breaking for N-Queens

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
>