Dynamic variable elimination during propagation solving

ABSTRACT

Constraint propagation solvers interleave propagation (removing impossible values from variables domains) with search. Propagation is performed by executing propagators (removing values) implementing constraints (defining impossible values). In order to specify constraint problems with a propagation solver often many new intermediate variables need to be introduced. Each variable plays a role in calculating the value of some expression. But as search proceeds not all of these expressions will be of interest any longer, but the propagators implementing them will remain active. In this paper we show how we can analyse the propagation graph of the solver in linear time to determine intermediate variables that can be removed without effecting the result. Experiments show that applying this analysis can reduce the space and time requirements for constraint propagation on example problems

REFERENCES

• 1: Sebastian Brand and Roland H. C. Yap. Towards "Propagation = Logic + Control". In Sandro Etalle and Miroslaw Truszczynski, editors, Logic Programming, 22nd International Conference, pages 102--116, 2006.
• 2: Chiu Wo Choi,Warwick Harvey, Jimmy Ho-Man Lee, and Peter J. Stuckey. Finite domain bounds consistency revisited. In AI 2006: Advances in Artificial Intelligence, volume 4304 of Lecture Notes in Computer Science, pages 49--58. Springer-Verlag, Berlin, Germany, 2006.
• 3: CSPLib. CSPLib: a problem library for constraints, 2006. Available from http://www.csplib.org.
• 4: Andreas Fordan , Roland H. C. Yap, Early Projection in CLP(R), Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming, p.177-191, October 26-30, 1998
• 5: Gecode Team. Gecode: Generic constraint development environment, 2006. Available from http://www.gecode.org.
• 6: Ian P. Gent, Chris Jefferson, and Ian Miguel. Watched literals for constraint propagation in Minion. In Frédéric Benhamou, editor, Twelfth International Conference on Principles and Practice of Constraint Programming, volume 4204 of LNCS, pages 182--197, Nantes, France, September 2006. Springer.
• 7: Joxan Jaffar , Spiro Michaylov , Peter J. Stuckey , Roland H. C. Yap, The CLP( R ) language and system, ACM Transactions on Programming Languages and Systems (TOPLAS), v.14 n.3, p.339-395, July 1992 [doi>10.1145/129393.129398]
• 8: Mikael Z. Lagerkvist and Christian Schulte. Advisors for incremental propagation. In Christian Bessière, editor, Thirteenth International Conference on Principles and Practice of Constraint Programming, Lecture Notes in Computer Science, pages 409--422, Providence, RI, USA, September 2007. Springer-Verlag.
• 9: Andrew D. Macdonald , Peter J. Stuckey , Roland H. C. Yap, Redundancy of variables in CLD R , Proceedings of the 1993 international symposium on Logic programming, p.75-93, December 1993, Vancouver, British Columbia, Canada
• 10: Alan K. Mackworth. Consistency in networks of relations. Artificial Intelligence, 8(1):99--118, 1977.
• 11: Jean-François Puget andMichel Leconte. Beyond the glass box: Constraints as objects. In John Lloyd, editor, Proceedings of the International Symposium on Logic Programming, pages 513--527, Portland, OR, USA, December 1995. The MIT Press.
• 12: Christian Schulte. Programming Constraint Services, volume 2302 of Lecture Notes in Artificial Intelligence. Springer-Verlag, 2002.
• 13: Christian Schulte and Peter J. Stuckey. Efficient constraint propagation engines. Transactions on Programming Languages and Systems, 2008. To appear.
• 14: Christian Schulte and Peter J. Stuckey. Speeding up constraint propagation. In M. Wallace, editor, Proceedings of the International Conference on Principle and Practice of Constraint Programming, volume 3258 of LNCS, pages 619--633. Springer-Verlag, 2004.
• 15: Christian Thiffault, Fahiem Bacchus, and Toby Walsh. Solving non-clausal formulas with DPLL search. In Mark Wallace, editor, Principles and Practice of Constraint Programming - CP 2004, 10th International Conference, pages 663--678, 2004.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Constraint and logic languages

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Constraints

General Terms:
Design, Experimentation, Languages

Keywords:
analysis, constraint (logic) programming, constraint propagation, redundancy