Hi David,
To quote from the doc:
"Domain-consistent linear equations have exponential complexity, so
use with care!"
Maybe we should be even more explicit: never use it for anything that has
more than four values per variable ;-( The cost of enforcing domain
consistency is O(d^n) for n variables with maximal domain size d, where the
worst case is the average case if the linear equation has unit coefficients.
Given that the domains you are using are large and you have unit
coefficients, you are just stuck in a slow finite loop! The implementation
in Gecode is kind of naïve, but there is little one can do given that
propagation is NP complete.
I am always tempted to remove domain-consistent linear as it is so
misleading.
Cheers
Christian
--
Christian Schulte, www.ict.kth.se/~cschulte/
-----Original Message-----
From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf
Of David Rijsman
Sent: Monday, December 10, 2007 5:15 PM
To: [EMAIL PROTECTED]
Subject: [gecode-users] Linear constraint on propagation level ILC_DOM
infinite loop
In Gecode 2.0.0 the following code seems to get stuck in an infinite loop:
template <class Val, class View> ExecStatus
DomEq<Val,View>::propagate(Space* home)
Am I missing something or doing something wrong, other propagation
levels seem to work correct.
---------------------------------------------------------
#include "gecode/minimodel.hh"
class TestCase : public Gecode::Space {
protected:
const int n;
Gecode::IntVarArray x;
public:
/// Actual model
TestCase()
: n(3),
x(this,n)
{
x[0].init( this, 0, 7*60*24 );
x[1].init( this, 0, 7*60*24 );
x[2].init( this, 0, 7*60*24 );
Gecode::IntVarArgs variables( 3 );
variables[0] = x[0];
variables[1] = x[1];
variables[2] = x[2];
Gecode::IntArgs arguments( 3 );
arguments[0] = 1;
arguments[1] = -1;
arguments[2] = -1;
Gecode::linear( this, arguments, x, Gecode::IntRelType::IRT_EQ, 0,
Gecode::ICL_DOM);
this->status();
}
TestCase(bool share, TestCase& s):
Space(share,s), n(s.n)
{
x.update(this, share, s.x);
}
/// Perform copying during cloning
virtual Space* copy(bool share)
{
return new TestCase(share,*this);
}
};
int main(int argc, char** argv)
{
TestCase();
return 0;
}
_______________________________________________
Gecode users mailing list
[EMAIL PROTECTED]
https://www.gecode.org/mailman/listinfo/gecode-users
_______________________________________________
Gecode users mailing list
[EMAIL PROTECTED]
https://www.gecode.org/mailman/listinfo/gecode-users
