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, negate...@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 <cschu...@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-boun...@gecode.org [mailto:users-boun...@gecode.org] On Behalf
Of negate...@gmail.com
Sent: Monday, April 21, 2014 02:47 AM
To: users@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@gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users
_______________________________________________
Gecode users mailing list
users@gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users
_______________________________________________
Gecode users mailing list
users@gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users
