Esta página em português Ajuda Autenticar-se
You are here: Start > PRODEI009
Authentication

Site map
Options

# Constraint Programming for Combinatory Optimization

 Code: PRODEI009 Acronym: PROC

Keywords
Classification Keyword
OFICIAL Science and Technology Programming

## Instance: 2018/2019 - 1S

 Active? Yes Responsible unit: Department of Informatics Engineering Course/CS Responsible: Doctoral Program in Informatics Engineering

### Cycles of Study/Courses

Acronym No. of Students Study Plan Curricular Years Credits UCN Credits ECTS Contact hours Total Time
PRODEI 2 Syllabus 1 - 6 28 162

### Teaching - Hours

 Recitations: 2,00
Type Teacher Classes Hour
Recitations Totals 1 2,00
Henrique Daniel de Avelar Lopes Cardoso 2,00

### Teaching language

Suitable for English-speaking students

### Objectives

The investment made by companies / institutions in the development of information systems to support their operations allows them to collect more and better data on these operations. This information enables a better understanding of how the organization works and creates opportunities to optimize its processes. This Course focuses on an approach for solving optimization problems, constraint programming.

Thus, the main objectives of this Course (UC) are:

• Motivate for the use of constraint programming techniques for solving complex optimization problems
• Develop the ability to properly utilize these techniques and the tools that implement them to solve real problems.

Percentage distribution:

• Scientific component: 70%
• Technological component: 30%

### Learning outcomes and competences

Upon completion of the course, a student should be able to:

• Identify combinatorial problems and classify them according to the known categories
• Create linear programming and integer programming models for an optimization problem
• Describe the process of problem solving used in constraint programming languages
• Describe the effects of constraint propagation algorithm on a network of constraints
• Differentiate constraing programming languages based on different paradigms
• Compare  solutions for the same problem based on constraint and mathematical programming
• Create a constraint model for an optimization problem by choosing variables, constraints, research methods and optimization criteria and develop a prototype application using constraint programming.

Presencial

### Program

• Combinatorial problems. Classes of problems. Models.

• Mathematical programming. Models of linear programming and integer programming.

• Constraints. Domains. Modelling with constraints.

• Constraints on operations. Simplification of constraints. Consistency. Solutions.

• Constraint models for combinatorial problems.

• Constraint programming languages. Logic Constraint Programming.

• Development of constraints for categories of problems. Global constraints.

• Optimization. Search. Complete and incomplete methods.

### Mandatory literature

Rina Dechter; Constraint Processing, Morgan Kaufmann, 2003
Kim Marriott, Peter J. Stuckey; Programming with Constraints- An Introduction, MIT Press, 1998
Krysztof R. Apt; Principles of Constraint Programming, Cambridge University Press, 2003

### Teaching methods and learning activities

Lessons combine the presentation of the themes of the course with a discussion of selected papers, as well as of the development of the course assignments.

The evaluation is distributed and consists of two practical assignments.

ECLiPSe

### Evaluation Type

Distributed evaluation without final exam

### Assessment Components

Designation Weight (%)
Participação presencial 0,00
Trabalho escrito 50,00
Trabalho laboratorial 50,00
Total: 100,00

### Amount of time allocated to each course unit

Designation Time (hours)
Elaboração de projeto 74,00
Elaboração de relatório/dissertação/tese 34,00
Frequência das aulas 54,00
Total: 162,00

### Calculation formula of final grade

0.50* Grade of assignment 1 + 0.5 * Grade of assignment 2

### Examinations or Special Assignments

The course requires the completion of two practical assignments:

• survey on the state of art in a sub-area of programming with constraints
• development of a constraint programming solution to a practical problem.

### Special assessment (TE, DA, ...)

Students with worker statute or equivalent must carry out the projects.

### Classification improvement

The improvement of the distributed evaluation can be made in the following edition of the course.