[gecode-users] Linear constraint on propagation level ILC_DOM infinite loop

[David Rijsman]

Hi Christian,

that seems to be the case, should have read more carefully, 10080^3
pretty much felt like an infinite loop,

thanks,

David

On Dec 10, 2007 5:34 PM, Christian Schulte <cschulte at kth.se> wrote:
> 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: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
> Of David Rijsman
> Sent: Monday, December 10, 2007 5:15 PM
> To: users at gecode.org
> 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
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
>
>