[gecode-users] Linear constraints

[Christian Schulte]

The only interesting case is equality, where bounds and domain propagation
really differ vastly. For inequalities bounds and domain propagation
coincides (see the references below), and for disequality there is only
domain propagation in Gecode (as pure bounds propagation is actually more
difficult to implement and is less efficient).

 

Hence in the following I only talk about equality.

 

Bounds is linear, domain is exponential (O(d^n) for domain size s and n
variables). 

 

Domain in Gecode is naive, just scanning all possible assignments (with some
bounds reasoning).

 

For propagating bounds linear (achieving bounds(R) consistency in Gecode and
not bounds(Z) for equality), see for example:

 
http://web.it.kth.se/~cschulte/paper.html?id=SchulteStuckey:TOPLAS:2005

 

And also (which is mentioned in Modeling with Gecode):

@InCollection{bounds-consistency,

  author =              {Chiu Wo Choi and Warwick Harvey and Jimmy Ho-Man
Lee and Peter J. Stuckey},

  title =  {Finite Domain Bounds Consistency Revisited},

  volume =       {4304},

  year = 2006,

  Pages        = "49--58",

  booktitle    = "AI 2006: Advances in Artificial Intelligence",

  series       = "Lecture Notes in Computer Science",

  publisher    = "Springer Verlag",

}

 

Christian

 

--

Christian Schulte, www.ict.kth.se/~cschulte/

 

From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Mauricio Toro
Sent: Thursday, March 04, 2010 5:39 PM
To: gecode list
Subject: [gecode-users] Linear constraints

 

Hello,

 

I am using linear constraints, reified and non-reified versions, and 

I have problems to choose between domain propagation and

bound propagation. Where can I find further information about each

type of propagation and their complexities in time? I already

looked at the information provided in the documentation.

 

Thank you,

 

Mauricio

-- 
Mauricio TORO BERMUDEZ

Research Postgraduate Student (Ph.D)
Computer Science Research Laboratory of Bordeaux (LABRI)
University of Bordeaux 1: Science and Technology

http://www.labri.fr/perso/mtoro/

351, cours de la Libération
F-33405 Talence Cedex. France.
Phone: (+33) 5 4000 24 85
Fax: (+33) 5 4000 66 69

Please don't print this e-mail unless you really need to.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20100304/8451d316/attachment.htm>