I reran by adjusting the -c-d and -a-d parameters and the time did go linear. I found this paper really helpful in explaining the concepts behind the parameters - "Maintaining State in Propagation Solvers”, given that the authors actively develop gecode :)..thanks
On Apr 24, 2014, at 12:53 AM, Guido Tack <t...@gecode.org> wrote: > Hi, > > Jean-Noel's observation is correct that copying introduces a linear factor > into the runtime. By default, copies are created every 8 steps down a > branch. You can set the recomputation parameters on the command line, using > -c-d and -a-d, if you add a call to > > opt.parse(argc,argv); > > To completely disable copying, set both distances to something higher than > the number of variables, e.g. -c-d 1000000 -a-d 1000000. In your particular > case, where there is no real search (since you don't have constraints), that > should change the runtime from quadratic to linear. > > However, in a problem that requires backtracking, you still need to create at > least one copy per failure, so you can still get that quadratic runtime > behaviour. > > Cheers, > Guido > > -- > Guido Tack > http://www.csse.monash.edu/~guidot/ > > > > On 24 Apr 2014, at 3:20 am, negate...@gmail.com wrote: > >> The time seems quadratic not exponential. I misspoke on that. >> >>> I think that one way to check this would be to completely disable copying >>> and replace it by recomputation. I am not sure how this is accomplished >>> though >> >> Would replacing the returning *this in the copy() method accomplish this ? >> >> >> On Apr 23, 2014, at 9:32, Jean-Noël Monette <jean-noel.mone...@it.uu.se> >> wrote: >> >>> Hi, >>> >>> Here is my understanding of your problem. If you have N variables, you will >>> need N decisions to reach a "solution". And at each decision, Gecode will >>> copy the whole model, that is N variables (Christian, correct if I am >>> wrong). So the time spent should be at least quadratic in the number of >>> variables. I am not sure whether the numbers you gave correspond much more >>> to an exponential increase rather than to a quadratic increase. So this >>> could be the explanation of your problem. I think that one way to check >>> this would be to completely disable copying and replace it by >>> recomputation. I am not sure how this is accomplished though. >>> >>> Cheers, >>> >>> Jean-Noël >>> >>> >>> On 23/04/14 17:58, negate...@gmail.com wrote: >>>> The statistics reveal that the “Peak depth” and “Nodes” are the same as >>>> the number of variables. Where can I get the number of “Search steps” ? >>>> My model did not have *any* constraints (model is copied below).I modified >>>> the bounds of the variables to see if the bounds made a difference in the >>>> solution time, but it did not. >>>> MODEL - >>>> class Money : public Script { >>>> protected: >>>> /// Number of letters >>>> static const int nl = 70000; // <---- This number corresponds >>>> with NVars listed above. >>>> /// Array of letters >>>> IntVarArray le; >>>> public: >>>> /// Model variants >>>> enum { >>>> MODEL_SINGLE, ///< Use single linear equation >>>> MODEL_CARRY ///< Use carries >>>> }; >>>> /// Actual model >>>> Money(const Options& opt) : le(*this,nl,0,65535) { // >>>> <----------BOUNDS for integer variable >>>> Rnd rnd(314) ; >>>> branch(*this, le, INT_VAR_SIZE_MIN(), INT_VAL_RND(rnd)); // >>>> <-------Random numbers to integers. >>>> } >>>> /// Print solution >>>> virtual void >>>> print(std::ostream& os) const { >>>> // os << "\t" << le << std::endl; >>>> } >>>> >>>> /// Constructor for cloning \a s >>>> Money(bool share, Money& s) : Script(share,s) { >>>> le.update(*this, share, s.le); >>>> } >>>> /// Copy during cloning >>>> virtual Space* >>>> copy(bool share) { >>>> return new Money(share,*this); >>>> } >>>> }; >>>> >>>> /** \brief Main-function >>>> * \relates Money >>>> */ >>>> int >>>> main(int argc, char* argv[]) { >>>> Options opt("SEND+?MORE=MONEY"); >>>> opt.model(Money::MODEL_SINGLE); >>>> opt.solutions(1); >>>> Script::run<Money,DFS,Options>(opt); >>>> std::cout << "--- \n" ; >>>> return 0; >>>> } >>>> On Apr 21, 2014, at 4:12 AM, Christian Schulte <cschu...@kth.se> wrote: >>>> >>>>> Just check the number of search steps needed, it can tell you something >>>>> more >>>>> important than time. >>>>> >>>>> Then (I am guessing here), given that your model is based on money it has >>>>> lost of linear constraints in it, right? There you will only get >>>>> propagation >>>>> if by branching either the lower or upper bound of the values for a >>>>> variable >>>>> changes. If you just randomize you are likely to choose an inner value >>>>> which >>>>> might not give that much propagation. >>>>> >>>>> Best >>>>> Christian >>>>> >>>>> -- >>>>> Christian Schulte, KTH, web.it.kth.se/~cschulte/ >>>>> >>>>> -----Original Message----- >>>>> From: users-boun...@gecode.org [mailto:users-boun...@gecode.org] On Behalf >>>>> Of negate...@gmail.com >>>>> Sent: Monday, April 21, 2014 02:47 AM >>>>> To: users@gecode.org >>>>> Subject: [gecode-users] Integer Variable Randomization >>>>> >>>>> Hi, I'm seeing an exponential time increase in the time to just randomize >>>>> integer variables. My test program is based on "examples/money.cpp" , and >>>>> I >>>>> removed the constraints and simply randomize the integer variables by >>>>> using >>>>> INT_VAL_RND() >>>>> -> branch(*this, le, INT_VAR_SIZE_MIN(), INT_VAL_RND(rnd)); >>>>> Is the exponential increase in time with the number of integer random >>>>> variables in Gecode expected ? and if so, why. And can this be improved by >>>>> modifying the model ? >>>>> Thanks.. >>>>> >>>>> NVars SolveTime(in Seconds) >>>>> 10000 0.734 >>>>> 20000 3.267 >>>>> 30000 7.67 >>>>> 40000 18.262 >>>>> 50000 31.274 >>>>> 60000 50.674 >>>>> 70000 73.82 >>>>> >>>>> Complete Test program - >>>>> >>>>> #include <gecode/driver.hh> >>>>> #include <gecode/int.hh> >>>>> #include <gecode/minimodel.hh> >>>>> >>>>> using namespace Gecode; >>>>> >>>>> class Money : public Script { >>>>> protected: >>>>> /// Number of letters >>>>> static const int nl = 70000; // <---- This number corresponds >>>>> with >>>>> NVars listed above. >>>>> /// Array of letters >>>>> IntVarArray le; >>>>> public: >>>>> /// Model variants >>>>> enum { >>>>> MODEL_SINGLE, ///< Use single linear equation >>>>> MODEL_CARRY ///< Use carries >>>>> }; >>>>> /// Actual model >>>>> Money(const Options& opt) : le(*this,nl,0,65535) { // <---------- >>>>> BOUNDS for integer variable >>>>> Rnd rnd(314) ; >>>>> branch(*this, le, INT_VAR_SIZE_MIN(), INT_VAL_RND(rnd)); // >>>>> <------- >>>>> Random numbers to integers. >>>>> } >>>>> /// Print solution >>>>> virtual void >>>>> print(std::ostream& os) const { >>>>> // os << "\t" << le << std::endl; >>>>> } >>>>> >>>>> /// Constructor for cloning \a s >>>>> Money(bool share, Money& s) : Script(share,s) { >>>>> le.update(*this, share, s.le); >>>>> } >>>>> /// Copy during cloning >>>>> virtual Space* >>>>> copy(bool share) { >>>>> return new Money(share,*this); >>>>> } >>>>> }; >>>>> >>>>> /** \brief Main-function >>>>> * \relates Money >>>>> */ >>>>> int >>>>> main(int argc, char* argv[]) { >>>>> Options opt("SEND+?MORE=MONEY"); >>>>> opt.model(Money::MODEL_SINGLE); >>>>> opt.solutions(1); >>>>> Script::run<Money,DFS,Options>(opt); >>>>> std::cout << "--- \n" ; >>>>> return 0; >>>>> } >>>>> >>>>> // STATISTICS: example-any >>>>> >>>>> >>>>> _______________________________________________ >>>>> 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 >>>> >>> >>> >>> _______________________________________________ >>> 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 >
_______________________________________________ Gecode users mailing list users@gecode.org https://www.gecode.org/mailman/listinfo/gecode-users
