[gecode-users] Integer Variable Randomization
negate273 at gmail.com
negate273 at gmail.com
Fri Apr 25 06:46:32 CEST 2014
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 <tack at 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, negate273 at 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.monette at 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, negate273 at 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 <cschulte at 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-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
>>>>> Of negate273 at gmail.com
>>>>> Sent: Monday, April 21, 2014 02:47 AM
>>>>> To: users at 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 at gecode.org
>>>>> https://www.gecode.org/mailman/listinfo/gecode-users
>>>>>
>>>>
>>>> _______________________________________________
>>>> Gecode users mailing list
>>>> users at gecode.org
>>>> https://www.gecode.org/mailman/listinfo/gecode-users
>>>>
>>>
>>>
>>> _______________________________________________
>>> Gecode users mailing list
>>> users at gecode.org
>>> https://www.gecode.org/mailman/listinfo/gecode-users
>> _______________________________________________
>> Gecode users mailing list
>> users at gecode.org
>> https://www.gecode.org/mailman/listinfo/gecode-users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20140424/f1f4cfb7/attachment-0001.html>
More information about the users
mailing list