CONSTRAINT PROGRAMMING

Credits: 
6
Year of erogation: 
2021/2022
Unit Coordinator: 
Disciplinary Sector: 
Computer Science
Semester: 
First semester
Year of study: 
2
Language of instruction: 

English

Learning outcomes of the course unit

The course offers the theoretical basis for problem modeling and solving through constraint programming.
The course is structured into frontal lessons and a set of practical implementation sessions.

Taking Dublin Indicators into account:

Knowledge and understanding
The course introduces the concepts related to constraint programming. Particular emphasis is devoted to model analysis, constraint propagation and constraint solving. Classes, references and scientific papers and in English language.

Applying knowledge and understanding
Theoretical bases are always exemplified through practical problems implementations. The companion exercises are focused on problem solving and testing the comprehension of proposed methods, with particular focus an modeling and performances.

Making judgments
The exercises, which are proposed in relation to the theoretical part presented in class, can be solved individually or in groups. The critical judgment, also extended to classmates, favors the development of specific skills in students to enable problem solving and team work skills. Often the exercises can be solved in many different ways and listening to the solutions proposed by other allows students to develop the ability to identify common structures and best practices.

Communication skills
Discussions about different methods to solve the same problem allow students to improve communication skills (in English during classes).

Learning skills
The capability to locate and comprehend externar resources and scientific literature allows to develop autonomous learning skills. The student acquires adaptation skills and he/she is able to apply the most suitable models to the problem at hand.

Course contents summary

The course covers the basis of constraint programming, as declarative programming paradigm; programming techniques, problem modeling and constraint resolution in search. Practical examples of complex problems are modelled and solved.

Course contents

Introduction to declarative programming.
Constraint Satisfaction Problems
Logical variables, relations
Constraint resolution: consistency and constraint propagation
Resolution techniques in search
CSP/COP (optimization)
Global constraints
Local search
Examples of problems and their resolution strategies

Recommended readings

Online resources

Teaching methods

Classes, group discussions, small group problem solving

Assessment methods and criteria

Learning outcomes and methods of verification
Being able to understand and make appropriate use of techniques related to constraint programming. Being able to model a non-CS problem and implement it into a constraint framework. Being able to select the most suitable constraints for correct and efficient solutions.

Learning assessment/examination
The exam requires the development (in groups of 2/3 students) of a project and public discussion. The project is assigned to students and references to literature with models and/or resolution techniques are provided.