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

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

GOALS

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

CONTENTS

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