Go to:
Logótipo
You are here: Start > PRODEI009

Constraint Programming for Combinatory Optimization

Code: PRODEI009     Acronym: PROC

Keywords
Classification Keyword
OFICIAL Science and Technology Programming

Instance: 2014/2015 - 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 0 Syllabus 1 - 6 54 162

Teaching - Hours

Recitations: 3,00
Type Teacher Classes Hour
Recitations Totals 1 3,00
Henrique Daniel de Avelar Lopes Cardoso 1,50
Carlos Manuel Milheiro de Oliveira Pinto Soares 1,50

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.

Working method

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.

Software

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.

 

Recommend this page Top
Copyright 1996-2024 © Faculdade de Engenharia da Universidade do Porto  I Terms and Conditions  I Accessibility  I Index A-Z  I Guest Book
Page generated on: 2024-03-28 at 23:01:10 | Acceptable Use Policy | Data Protection Policy | Complaint Portal