[gecode-users] Nogoods limit

[Christian Schulte]

Hi Kish,

Oh, I see. 

How do you know that the no-goods do not work? MPG tries to explain that
even with using no-goods you might not get the guarantee that a solution is
only found once. So, it might not terminate when restarting (where I am
guessing that you search for _all_ solutions, right?).

Best
Christian

--
Christian Schulte, Professor of Computer Science, KTH,
www.ict.kth.se/~cschulte/


-----Original Message-----
From: Kish Shen [mailto:kisshen at cisco.com] 
Sent: Friday, November 22, 2013 7:28 PM
To: cschulte at kth.se; users at gecode.org
Subject: Re: [gecode-users] Nogoods limit

Hi Christian,

I think I am using the predefined branchers, i.e. I just do:

branch(*solver, vars, varselect, valchoice);

I think this is using the pre-defined branchers?

and then I set up a search engine as I showed previously.

Thanks and cheers,

Kish

On 22/11/2013 14:04, Christian Schulte wrote:
> Hi Kish,
>
> Let me guess: you are not using the pre-defined branchers from Gecode 
> or do you? If you use your own branchers you have to add support that 
> actually generates the no-goods.
>
> Cheers
> Christian
>
> --
> Christian Schulte, Professor of Computer Science, KTH, 
> www.ict.kth.se/~cschulte/
>
>
> -----Original Message-----
> From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On 
> Behalf Of Kish Shen
> Sent: Friday, November 22, 2013 6:25 AM
> To: users at gecode.org
> Subject: [gecode-users] Nogoods limit
>
> Hi,
>
> I have now got restart search implemented, thanks to help from 
> Christian. I finally decided to implement restart DFS as a separate 
> search method in my interface, and only allow one solution in this 
> case, because getting the previous solution posted as a no-goods 
> looked quite difficult, and probably not a good idea for most search
anyway.
>
> I ran some tests, and it seems that the restart with cutoff is 
> working, but the no-goods limit is not:
>
> I tested the search with an N-Queens problem, using INT_VAR_NONE and 
> INT_VAL_MIN for variable and value selection, and a constant cutoff.
> The idea here is that every single restart (without no-goods) should 
> perform exactly the same search, so if the cutoff is set below the 
> number of failures before the solution is found, then the search will not
terminate.
> This is indeed the case, e.g. for N=8, with the cutoff set at 23, then 
> the search does not terminate, but with cutoff=24, a solution is 
> returned. Also, using a geometric cutoff, a solution is also found, 
> even with a low initial cutoff. So this seems to show that the restart 
> with cutoff is working as expected.
>
> However, it seems that I can't get the nogoods_limit to work -- using 
> the same 8-Queens example, with a constant cutoff of 23, I expect that 
> restarts with no-goods should be able to find the solution. However, 
> even when I set the nogoods_limit very high (1000), the search does 
> not terminate. So I assume this means my code for nogoods_limit is not
working...
>
> I setup the restart DFS search engine as follows:
>
> sengine = new GecodeRBS<DFS>(solver, o);
>
> where o is a Search::Options, and has o.nogoods_limit set (I verified 
> this by printing o.nogoods_limit just before calling the above).
>
> GecodeRBS is based on the code Chrisitan sent me:
>
> template<template<class> class E>
> class GecodeRBS : public GecodeEngineBase {
> protected:
>      RBS<E,GecodeSpace> e;
>
> public:
>      GecodeRBS(GecodeSpace* solver, const Search::Options& o) :
> e(solver,o) {}
> .....
> }
>
> (there might be typos: I typed the above in by hand, as cutting and 
> pasting the actual code (in an VNC window) and my mailer running under 
> Windows is a
> pain)
>
> I have not defined master() in GecodeSpace, as I think the default 
> does what I need -- nogoods will be posted, so if nogood_limits is 
> set,  then nogoods should be collected and posted in the default master().
>
> So I expected that if o.nogoods_limit is set in my sengine setup code, 
> then nogoods will be posted by master, and with the limit set to 1000, 
> all nogoods in my 8-Queens examples should be collected and posted, so 
> the search should terminate. So I don't know why the search is not
terminating.
> Am I doing something wrong in my code, or is my understanding of the 
> expected behaviour incorrect?
>
> I am using Gecode 4.2.0.
>
> Cheers,
>
> Kish
>
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
>