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
