Resources

Foundations of Constraint Satisfaction

 

Home | Author | Lectures | Resources

 

Basic resources

  • Lecture notes [PDF]
  • A list of references [PDF]
  • Constraint Programming - What is behind? [PDF]
    R. Barták, in J. Figwer (editor) Proceedings of the Workshop on Constraint Programming in Decision and Control, June 1999, Poland.
  • Theory and Practice of Constraint Propagation [PDF]
    R. Barták, in J. Figwer (editor) Proceedings of the 3rd Workshop on Constraint Programming in Decision and Control, June 2001, Poland.
  • On-line Guide to Constraint Programming, 1998 [WWW]
  • Constraints Archive [WWW]
  • P. Van Hentenryck: Constraint Satisfaction in Logic Programming, MIT Press, 1989
  • E. Tsang: Foundations of Constraint Satisfaction, Academic Press, 1993
  • K. Marriott, P.J. Stuckey: Programming with Constraints: An Introduction, MIT Press, 1998

Thema-based resources

Binarisation of constraints

  • On the equivalence of constraint satisfaction problems
    F. Rossi, V. Dahr and C. Petrie, in Proc. European Conference on Artificial Intelligence (ECAI-90), Stockholm, 1990. Also MCC Technical Report ACT-AI-222-89.
  • On the conversion between Non-Binary and Binary Constraint Satisfaction Problems
    F. Bacchus, P. van Beek, in Proc. National Conference on Artifical Intelligence (AAAI-98), Madison, Wisconsin, 1998.
  • Encodings of Non-Binary Constraint Satisfaction Problems
    K. Stergiou, T. Walsh, in Proc. National Conference on Artifical Intelligence (AAAI-99), Orlando, Florida, 1999.
  • Using auxiliary variables and implied constraints to model non-binary problems
    B. Smith, K. Stergiou, T. Walsh, in Proc. National Conference on Artifical Intelligence (AAAI-00), Austin, Texas, 2000.
  • Non-Binary Constraints
    C. Bessiere, in Proc. Principles and Practice of Constraint Programming (CP-99), Alexandria, Virginia, USA, 1999.

Search algorithms

  • Backtracking algorithms for constraint satisfaction problems; a survey
    R. Dechter, D. Frost, in Constraints, International Journal, 1998.
  • Dynamic Backtracking
    M.L. Ginsberg, in Journal of Artificial Intelligence Research 1, pages 25-46, 1993.
  • Iterative Broadening
    M.L. Ginsberg, W.D. Harvey, In AAAI Proceedings, 1990.
  • Limited Discrepancy Search
    W.D. Harvey and M.L. Ginsberg, in Proceedings of IJCAI95, pages 607-613, 1995.

Consistency algorithms

  • Consistency in networks of relations [AC1-3, PC1-2]
    A.K. Mackworth, in Artificial Intelligence 8, pages 99-118, 1977.
  • The complexity of some polynomial network consistency algorithms for constraint satisfaction problems [AC1-3, PC1-2]
    A.K. Mackworth and E.C. Freuder, in Artificial Intelligence 25, pages 65-74, 1985.
  • Arc and path consistency revised [AC4, PC3]
    R. Mohr and T.C. Henderson, in Artificial Intelligence 28, pages 225-233, 1986.
  • Arc consistency for factorable relations [AC5]
    M. Perlin, in Artificial Intelligence 53, pages 329-342, 1992.
  • A generic arc-consistency algorithm and its specializations [AC5]
    P. Van Hentenryck, Y. Deville, and C.-M. Teng, in Artificial Intelligence 57, pages 291-321, 1992.
  • Arc-consistency and arc-consistency again [AC6]
    C. Bessiere, in Artificial Intelligence 65, pages 179-190, 1994.
  • Using constraint metaknowledge to reduce arc consistency computation [AC7]
    C. Bessiere, E.C. Freuder, and J.-R. Régin, in Artificial Intelligence 107, pages 125-148, 1999.
  • Comments on Mohr and Henderson's path consistency algorithm [PC4]
    C. Han and C. Lee, in Artificial Intelligence 36, pages 125-130, 1988.
  • Path Consistency Revised [PC5]
    M. Singh, in Proceedings of the 7th IEEE International Converence on Tolls with Artificial Intelligence, pages 318-325, 1995.
  • Improving Domain Filtering using Restricted Path Consistency [RPC]
    P. Berlandier, in Proceedings of the IEEE CAIA-95, Los Angeles CA, 1995.
  • Neighborhood inverse consistency preprocessing [NIC]
    E. Freuder and C. D. Elfe, in Proceedings of the AAAI National Conference, pages 202-208, 1996.
  • Some practicable filtering techniques for the constraint satisfaction problem
    R. Debruyne and C. Bessi`ere, in Proceedings of the 15th IJCAI, pages 412-417, 1997.
  • Singleton Consistencies
    P. Prosser, K. Stergiou, T. Walsh, in Proc Principles and Practice of Constraint Programming (CP2000), pages 353-368, 2000.
  • A generic customizable framework for inverse local consistency
    G. Verfaillie, D. Martinez, and C. Bessiere, in Proceedings of the AAAI National Conference, pages 169-174, 1999.
  • A filtering algorithm for constraints of difference in CSPs
    J.C. R'egin, in AAAI-94, in Proceedings of the Twelfth National Conference on Artificial Intelligence, pages 362-367, 1994
 © 2002 Roman Barták

Foundations of Constraint Satisfaction