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

Hi Sergii,

As Helmut said, you probably need to try much smarter algorithms to 
solve N-Queens for large Ns.

However, specifically for gfd, your large memory consumption is almost 
certainly due to the cloning of the Gecode computation state. You can 
reduce the frequency of cloning (and thus the amount of memory consumed) 
by making the cloning_distance larger (the default is very small). 
Increasing the cloning_distance may also increase the execution times, 
but you said this is not the issue.

cloning_distance applies if you are doing the search in ECLiPSe -- which 
I think you are. You can change it with gfd_set_default/2.

Cheers,

Kish

> 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.
>
> The best result I've got so far is with gfd library, alldifferent
> constraints, most_constrained, indomain_median and credit search, without
> any symmetry breaking. Memory, not the processor speed, is the problem in
> this case - for N=5000 is eats all my 4GB + 6GB swap very fast. The model
> is an integer for every column.
>
> I tried different libraries for symmetry breaking: ldsb with ic and gfd (I
> had to change ldsb library slightly to make it work with gfd), sbds with ic
> and gfd (from the very recent 6.1 #161 release) and ic_gap_sbds and
> ic_gap_sbdd. Every library has settings for N-Queens in its documentation,
> so I used those.
>
> I haven't had any success with any of the symmetry breaking libraries.
> Using any of them seems to worsen speed or memory consumption greatly. Are
> there any results that symmetry breaking works for N-Queens in practice?
>
> Middle first rearrangement also works pretty bad compared to
> most_constrained.
>
> Any suggestions how to get better results than N=4000 with ECLiPSe (no code
> or pseudo-code please, because that would violate the course collaboration
> policy)?
>
> Sergii.
>
>
>
> ------------------------------------------------------------------------------
> 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
>