42034 - Problem Solving and Constraint Programming (RPAR) [UPC]

Type: S3 Course
Semester: Fall
Teaching Points: 15
Offer: Annual
Responsible Unit: CS-UPC
Responsible: Javier Larrosa
Language: English


In this course we take constraint programming as the problem solving method. The objective is that the student becomes familiar with a declarative programming paradigm that he/she can use in his/her research. In particular, the student must be able to determine if a given problem can be expressed as a constraint satisfaction problem. If so, the student must identify the different ways of modeling it. Finally, he/she must know the technology that is behind constraint programming tools


1. Introduction
2. Modeling
  • Decision problems
    • Constraint programming
    • SAT
  • Optimization problems
    • Soft constraint programming
    • Weighted SAT
3. Search
  • Local search
  • Systematic search
4. Inference
  • Aproximate inference
    • Local consistency
    • Search with local consistency
  • Exact inference
    • Adaptive consistency
    • Bucket elimination
5. Advanced topics