[gecode-users] Integer Variable Randomization
negate273 at gmail.com
negate273 at gmail.com
Wed Apr 23 19:20:56 CEST 2014
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20140423/b83acc08/attachment-0001.html>
More information about the users
mailing list