Maintaining State in Propagation Solvers
2009 (English)In: PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING / [ed] Gent, IP, Springer, 2009, Vol. 5732, 692-706 p.Conference paper (Refereed)
Constraint propagation solvers interleave propagation, removing impossible values from variable domains, with search. The solver state is modified during propagation. But search requires the solver to return to a previous state. Hence a, propagation solver must determine how to maintain state during propagation and forward and backward search. This paper sets out the possible ways in which a propagation solver call choose to maintain state, and the restrictions that such choices place on the resulting system. Experiments illustrate the result of various choices for the three principle state components of a solver: variables, propagators, and dependencies between them. This paper also provides the first realistic comparison of trailing versus copying for state restoration.
Place, publisher, year, edition, pages
Springer, 2009. Vol. 5732, 692-706 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 5732
IdentifiersURN: urn:nbn:se:kth:diva-70424DOI: 10.1007/978-3-642-04244-7_54ISI: 000273241200051ScopusID: 2-s2.0-70350376407ISBN: 978-3-642-04243-0OAI: oai:DiVA.org:kth-70424DiVA: diva2:486342
15th International Conference on Principles and Practice of Constraint Programming (CP 2009). Lisbon, PORTUGAL. SEP 20-24, 2009
QC 201201312012-01-302012-01-302012-01-31Bibliographically approved