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

Hi Sergii,

the point I was trying to make was that if you need your local search 
algorithm to scale up to very large instances, it is much more 
beneficial to think about initialization - indeed, constructing partial 
solutions - as this will get you much further than tweaking the settings 
or code of your local search method.

But of course the prerequisite for this, as you point out, is an 
understanding of both the general algorithm as well as the structure of 
the problem that you are trying to solve.

Cheers,
Thorsten


Am 05.07.2013 19:08, schrieb Sergii Dymchenko:
> Hi Thorsten,
>
> I used "diagonal" initialization: first queen on position 1, second on 
> position 2 and so on. After that I used queen swap as local moves, 
> that way the first of alldifferent constraints can be removed.
>
> I don't want to do complex initialization that gives almost a valid 
> placement because N-Queens is not really NP-hard and you can construct 
> explicit solutions very fast ( 
> http://en.wikipedia.org/wiki/N-queens#Explicit_solutions ). Doing 
> complex initialization is like partially constructing explicit 
> solution, and this doesn't help to learn how techniques and algorithms 
> work in general.
>
> Sergii.
>
>
> On Fri, Jul 5, 2013 at 2:36 AM, Thorsten Winterer 
> <thorsten_winterer_at_...126... <mailto:thorsten_winterer_at_...126...>> wrote:
>
>     Am 03.07.2013 08:55, schrieb Sergii Dymchenko:
>     > 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.
>
>
>     It often helps a lot if you can initialize the variables in a way that
>     gives your local search algorithm a head start. (though sometimes you
>     may find yourself in a local optimum straight away)
>
>     I tweaked Joachim's code a bit, changing the initialization such that
>     the first queen is on position 1, the second on 3 etc. This gives an
>     almost valid placement:
>
>              % initialize
>              N2 is integer(round(N/2)),
>              (
>                  foreacharg(X, Board), count(I, 1, _), param(N2)
>              do
>                  ( I =< N2 -> V is (I*2 - 1) ; V is (I - N2)*2 ),
>                  X tent_set V
>              ),
>
>
>     I also changed the code so that the neighbourhood size increases
>     when no
>     improving move was found in the last iteration. If the neighbourhood
>     becomes too large, a random move is made.
>
>              (
>                  fromto(V0,V1,V2,0),
>                  fromto(-1,LD,D,_),
>                  fromto(SampleSize,LS,S,_),
>                  param(Vars,N,N0,SampleSize,Violations)
>              do
>                  vs_random_worst(Vars, X),    % get a most violated
>     variable
>                  (
>                      (
>                          LD < 0,       % if last move was improvement
>                          S = SampleSize
>                      ;
>                          S0 is LS*10,  % or larger neighbourhood
>                          S0 =< N0,     % is not too large
>                          S = S0
>                       )
>                  ->
>                      % then find a best neighbour
>                      tent_minimize_random(   (
>     random_sample(1..N,S,I),
>                                                  X tent_set I
>                                              ),
>                                              Violations,
>                                              I
>                                          )
>                  ;
>                      % else make some random move
>                      random(R),
>                      I is (R mod N) + 1,
>                      S = SampleSize
>                  ),
>                  X tent_set I,
>                  Violations tent_get V2,
>                  D is V2-V1
>              ).
>
>
>     Here are the times for a couple of runs on my laptop:
>
>     ?- queens(30000, B).
>     B = [](1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, ...
>     Yes (0.49s cpu)
>     ?- queens(30000, B).
>     B = [](15306, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, ...
>     Yes (4.31s cpu)
>     ?- queens(30000, B).
>     B = [](1, 3, 5, 7, 9, 11, 13, 15, 17, 15351, 21, 23, ...
>     Yes (3.29s cpu)
>     ?- queens(30000, B).
>     B = [](1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, ...
>     Yes (6.64s cpu)
>
>
>     With a random initialization, the runtime was about 1.5 hours.
>
>     Cheers,
>     Thorsten
>
>
>
>     ------------------------------------------------------------------------------
>     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
>     <mailto:ECLiPSe-CLP-Users_at_lists.sourceforge.net>
>     https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users
>
>