Deriving Filtering Algorithms from Constraint Checkers

1. Amilhastre, J., Fargier, H., Marquis, P.: Consistency restoration and explanations in dynamic CSPs – application to configuration. Artificial Intelligence 135, 199–234 (2002)

   Article  MATH  MathSciNet  Google Scholar 

2. Beldiceanu, N.: Global constraints as graph properties on structured network of elementary constaints of the same type. In: Dechter, R. (ed.) CP 2000. LNCS, vol. 1894, pp. 52–66. Springer, Heidelberg (2000)

   Chapter  Google Scholar 

3. Beldiceanu, N.: Pruning for the minimum constraint family and for the number of distinct values constraint family. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 211–224. Springer, Heidelberg (2001)

   Chapter  Google Scholar 

4. Beldiceanu, N., Carlsson, M.: Revisiting the cardinality operator and introducing the cardinality-path constraint family. In: Codognet, P. (ed.) ICLP 2001. LNCS, vol. 2237, pp. 59–73. Springer, Heidelberg (2001)

   Chapter  Google Scholar 

5. Beldiceanu, N., Carlsson, M., Petit, T.: Deriving filtering algorithms from constraint checkers. Technical Report T2004-08, Swedish Institute of Computer Science (2004)

   Google Scholar 

6. Beldiceanu, N., Contejean, E.: Introducing global constraints in CHIP. Mathl. Comput. Modelling 20(12), 97–123 (1994)

   Article  MATH  Google Scholar 

7. Beldiceanu, N., Guo, Q., Thiel, S.: Non-overlapping constraints between convex polytopes. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 392–407. Springer, Heidelberg (2001)

   Chapter  Google Scholar 

8. Beldiceanu, N., Poder, E.: Cumulated profiles of minimum and maximum resource utilisation. In: Ninth Int. Conf. on Project Management and Scheduling, pp. 96–99 (2004)

   Google Scholar 

9. Berge, C.: Graphs and hypergraphs. Dunod, Paris (1970)

   Google Scholar 

10. Boigelot, B., Wolper, P.: Representing arithmetic constraints with finite automata: An overview. In: Stuckey, P.J. (ed.) ICLP 2002. LNCS, vol. 2401, pp. 1–19. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

11. Bourdais, S., Galinier, P., Pesant, G.: HIBISCUS: A constraint programming application to staff scheduling in health care. In: Rossi, F. (ed.) CP 2003. LNCS, vol. 2833, pp. 153–167. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

12. Carlsson, M., Beldiceanu, N.: From constraints to finite automata to filtering algorithms. In: Schmidt, D. (ed.) ESOP 2004. LNCS, vol. 2986, pp. 94–108. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

13. Carlsson, M., et al.: SICStus Prolog User’s Manual. Swedish Institute of Computer Science, 3.11 edition (January 2004), http://www.sics.se/sicstus/

14. Carlsson, M., Ottosson, G., Carlson, B.: An open-ended finite domain constraint solver. In: Hartel, P.H., Kuchen, H. (eds.) PLILP 1997. LNCS, vol. 1292, pp. 191–206. Springer, Heidelberg (1997)

    Chapter  Google Scholar 

15. Cohen, J.: Non-deterministic algorithms. ACM Computing Surveys 11(2), 79–94 (1979)

    Article  MATH  Google Scholar 

16. COSYTEC. CHIP Reference Manual, v5 edition (2003)

    Google Scholar 

17. Frisch, A., Hnich, B., Kızıltan, Z., Miguel, I., Walsh, T.: Global constraints for lexicographic orderings. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol. 2470, pp. 93–108. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

18. Gent, I.P., Walsh, T.: CSPLib: a benchmark library for constraints. Technical Report APES-09-1999, APES (1999), http://www.csplib.org

19. Van Hentenryck, P., Carillon, J.-P.: Generality vs. specificity: an experience with AI and OR techniques. In: National Conference on Artificial Intelligence, AAAI 1988 (1988)

    Google Scholar 

20. Janssen, P., Vilarem, M.-C.: Problèmes de satisfaction de contraintes: techniques de résolution et application à la synthèse de peptides. Research Report C.R.I.M., 54 (1988)

    Google Scholar 

21. Jégou, P.: Contribution à l’étude des problèmes de satisfaction de contraintes: algorithmes de propagation et de résolution. Propagation de contraintes dans les réseaux dynamiques. PhD Thesis (1991)

    Google Scholar 

22. Maher, M.: Analysis of a global contiguity constraint. In: Workshop on Rule-Based Constraint Reasoning and Programming, held along CP-2002 (2002)

    Google Scholar 

23. Milano, M.: Constraint and integer programming. Kluwer Academic Publishers, Dordrecht (2004)

    MATH  Google Scholar 

24. Ottosson, G., Thorsteinsson, E., Hooker, J.N.: Mixed global constraints and inference in hybrid IP-CLP solvers. In: CP 1999 Post-Conference Workshop on Large-Scale Combinatorial Optimization and Constraints, pp. 57–78 (1999)

    Google Scholar 

25. Pesant, G.: A regular language membership constraint for sequence of variables. In: Workshop on Modelling and Reformulation Constraint Satisfaction Problems, pp. 110–119 (2003)

    Google Scholar 

26. Petit, T., Régin, J.-C., Bessière, C.: Specific filtering algorithms for over-constrained problems. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 451–463. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

27. Le Provost, T., Wallace, M.: Domain-independent propagation. In: Proc. of the International Conference on Fifth Generation Computer Systems, pp. 1004–1011 (1992)

    Google Scholar 

28. Refalo, P.: Linear formulation of constraint programming models and hybrid solvers. In: Dechter, R. (ed.) CP 2000. LNCS, vol. 1894, pp. 369–383. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

29. Vempaty, N.R.: Solving constraint satisfaction problems using finite state automata. In: National Conference on Artificial Intelligence (AAAI 1992), pp. 453–458. AAAI Press, Menlo Park (1992)

    Google Scholar 

30. Woeginger, G.J.: Exact algorithms for NP-hard problems: A survey. In: Jünger, M., Reinelt, G., Rinaldi, G. (eds.) Combinatorial Optimization - Eureka, You Shrink! LNCS, vol. 2570, pp. 185–207. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

Download references