Constraint Programming for Combinatory Optimization
Keywords |
Classification |
Keyword |
OFICIAL |
Science and Technology Programming |
Instance: 2022/2023 - 1S
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 |
28 |
162 |
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.