Re: [gecode-users] Nogoods limit

Kish Shen Tue, 26 Nov 2013 11:17:28 -0800

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 usingrestart DFS without nogoods is that a positive nogoods_limit is set (infact for the restart DFS without nogoods, I set the limit to 0, eventhough this is the default, because I use the same call to Gecode inboth cases).

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

Without nogoods, the behaviour I see is as I expect -- with the cutoffbelow 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 23failures in this search before the solution was found.

To test the restart DFS with nogoods, I set the nogoods_limit in theoption to 23, reasoning that if any nogoods are posted, the restartedsearch will find a solution, because the cutoff is just below thethreshold where I do get a solution, and I expect the search on restartto be very similar, so even 1 nogoods should be sufficient for gettingaa solution. In any case, with the limit set to 1000, there should bemany nogoods that are collected, so the search not terminating wasunexpected.


Cheers,

Kish

Best
Christian

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


-----Original Message-----
From: Kish Shen [mailto:kiss...@cisco.com]
Sent: Friday, November 22, 2013 7:28 PM
To: cschu...@kth.se; users@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-boun...@gecode.org [mailto:users-boun...@gecode.org] On
Behalf Of Kish Shen
Sent: Friday, November 22, 2013 6:25 AM
To: users@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@gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users



_______________________________________________
Gecode users mailing list
users@gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users

Re: [gecode-users] Nogoods limit

Reply via email to