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: [email protected] [mailto:[email protected]] 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.
_______________________________________________ Gecode users mailing list [email protected] https://www.gecode.org/mailman/listinfo/gecode-users
