[gecode-users] Nogoods limit

[Kish Shen]

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
>