[gecode-users] Integer Variable Randomization

[negate273 at gmail.com]

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