[gecode-users] Nogoods limit

[Kish Shen]

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