[gecode-users] Integer Variable Randomization

[Christian Schulte]

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