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

From: Sergii Dymchenko <kit1980_at_gmail.com>
Date: Sat, 29 Jun 2013 15:46:54 -0700
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.
Received on Sat Jun 29 2013 - 22:47:02 CEST

This archive was generated by hypermail 2.2.0 : Tue Jul 02 2013 - 06:15:50 CEST