[gecode-users] Nogoods limit

[Christian Schulte]

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