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

[Christian Schulte]

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