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
