[gecode-users] Nogoods limit

[Kish Shen]

Hi Christian,


On 26/11/2013 15:59, Christian Schulte wrote:
> 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?).
>

No, I am searching for a single solution. The only difference with using 
restart DFS without nogoods is that a positive nogoods_limit is set (in 
fact for the restart DFS without nogoods, I set the limit to 0, even 
though this is the default, because I use the same call to Gecode in 
both cases).

The tests I was running were designed to show if my code for restart DFS 
is working or not. The reason I am using INT_VAR_NONE and INT_VAL_MIN is 
because I expect to get the same search on restart without nogoods, and 
even with nogoods, I expect the search to be similar, as INT_VAR_NONE 
choice is not affected by posting of constraints.

Without nogoods, the behaviour I see is as I expect -- with the cutoff 
below a certain value (24 in the case of the 8-Queens example I tried), 
the search does not terminate. I assume this is because there were 23 
failures in this search before the solution was found.

To test the restart DFS with nogoods, I set the nogoods_limit in the 
option to 23, reasoning that if any nogoods are posted, the restarted 
search will find a solution, because the cutoff is just below the 
threshold where I do get a solution, and I expect the search on restart 
to be very similar, so even 1 nogoods should be sufficient for getting 
aa solution. In any case, with the limit set to 1000, there should be 
many nogoods that are collected, so the search not terminating was 
unexpected.

Cheers,

Kish



> 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
>>
>
>