Constraint Programming for Combinatory Optimization
||Science and Technology Programming
Instance: 2018/2019 - 1S
Cycles of Study/Courses
||No. of Students
Suitable for English-speaking students
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.
- 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.
- 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.
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.
Distributed evaluation without final exam
Amount of time allocated to each course unit
|Elaboração de projeto
|Elaboração de relatório/dissertação/tese
|Frequência das aulas
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.
The improvement of the distributed evaluation can be made in the following edition of the course.