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?). 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
