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

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.
>
> 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
>


Helmut Simonis
4C, University College Cork
Ireland
Tel: +353 21 420 5967
web: www.4c.ucc.ie/~hsimonis