[gecode-users] Integer Variable Randomization

[negate273 at gmail.com]

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
>