1. Identification and allocation of the Curricular Unit
Escola de Ciências e Tecnologia
Mes. Int. em Engenharia Eletrotécnica e de Computadores
Curricular Unit code
Curricular Unit denomination
Otimização e algoritmos
Teacher in charge
Maria Adelaide da Cruz Cerveira
Other teachers from Curricular Unit
Maria Adelaide da Cruz Cerveira
2. General information
Teaching load / contact hours / ECTS
Autonomous work (hours)
Distribution of contact hours
Schedule of classes
OT - turma 1
Wednesday at 14h00m with duration of 01h30m
Wednesday at 14h00m with duration of 01h30m
TP - turma 1
Thursday at 16h00m with duration of 02h00m
Hours to students attendance
Maria Adelaide da Cruz Cerveira - 1º Semester
3. Objectives, syllabuses and teaching methods
Curricular Unit objectives and skills to develop (max. 1000 characters)
The main objective of this course is to provide students with fundamental knowledge of theory and algorithms for linear programming and Network Optimization.
The student must be able to:
- Model different real-life problems, within the context of Electrical and Computer Engineering, using Linear Programming (LP), Integer Linear programming (ILP) and network optimization models.
- solve problems by choosing the best-suited approach for each situation;
- use computational packages to solve problems;
- formulate the dual problem and interpret economically the dual variables;
- evaluate the robustness of the solutions through post-optimization and sensitivity analysis
- carry out a critical analysis of the obtained solutions strengthening the decision-making process;
- develop synthesis skills, critical thinking, written and oral communication, teamwork, usage of software, autonomy, and creativity.
Syllabus (max. 1000 characters)
Part I - Linear Optimization
Introduction to the general methodology used in Operations Research.
Mathematical Programming Modeling: linear programming problems (PPL) with continuous variables, PPL with integer and binary variables.
Modeling of linear optimization problems with applications in Electrical and Computer Engineering.
Introduction to the Mosel Modeling Language.
PPL resolution: graphical solution, by using the Simplex Algorithm and by using software (Excel and XPRESS).
Duality in linear programming. The economic interpretation of dual variables and sensitivity analysis.
Part II- Network Optimization
Fundamentals of graphs.
Shortest Path Problem.
Minimum Spanning Tree Problem
Maximum flow problem.
Modeling problems in the field of Electrical and Computer Engineering within Network Optimization.
Planning teaching activity (according to school Schedule) - (optional)
Demonstration of the Curricular Unit syllabus coherence with the intended learning outcomes (max. 1000 characters)
The syllabus on the course will allow students to acquire knowledge in the field of optimization and algorithms, in particular, in Linear Programming and Network Optimization. The focused subjects in the optimization field promote the development of skills concerning modeling, resolution and critical analysis of the obtained solutions in several types of problems, particularly in the context of Electrical and Computer Engineering.
Teaching / learning methodologies used (working methods, Curricular Unit running, resources, etc..) (max. 1000 characters)
The teaching of this course is based on theoretical-practical and tutorial classes.
The classes are made up of expository sessions, using the slide projection, which introduces the fundamental concepts associated with each of the topics of the syllabus. This exposure is continuously monitored by the illustration of examples, exercises, and case studies analysis in the context of Electrical and Computer Engineering.
Students are encouraged to apply the introduced concepts to solve the proposed exercises, including the use of suitable software. In all classes, students are asked to participate actively.
The assessment of this course includes performing theoretical-practical course works and written tests. The final classification is obtained by a weighted mean of the classifications obtained in the course works and written tests.
Demonstration of the consistency of teaching methodologies with the objectives of the Curricular Unit (max. 3000 characters)
The UC of Optimization and Algorithms is organized in a typology of theoretical-practical and tutorial classes, where the exposure of the syllabus, the bibliography, and the proposed exercises allow the student, jointly with a component of individual study, to assimilate theoretical concepts and understand their applicability.
In the classes, the concepts are introduced and its usefulness is discussed. Students are encouraged to participate more actively in the learning process, testing their knowledge by solving appropriated practical exercises that include the use of computer software. It is intended that students develop autonomous work skills.
4. Evaluation Methodology
Assessment modes, need to register prior to testing and transition conditions between modes
Concerning the assessment model of the course unit of Optimization and Algorithms, the students must take into account the following items.
1. Registration in the course unit
The registration on the theoretical-practical (TP) and tutorial orientation (OT) classes is mandatory and must be done in the SIDE (Information System for Education Support).
2. Registration in assessment tests
To obtain access to any assessment test, the students should be aware that, for successfully completing the course, they must:
2.1-be enrolled in one of the theoretical-practical classes and on the tutorial class;
2.2-be present, at least, in 70% of the total hours taught. Exceptions to the student workers and military students who are subject to a special regime;
3.3 must enroll in SIDE up to two working days prior to the test.
3. Modes of assessment
The students can be assessed in the following ways:
(a) Mode 1: continuous assessment;
(b) Mode 2: continuous assessment followed by complementary assessment;
(c) Mode 3: final assessment (by exam).
The continuous assessment (Mode 1) consists of a theoretical and practical component, through the accomplishment of two written tests (mini tests) during the period of classes and of a practical component, through the accomplishment of a practical team works.
Each one of the written tests will be rated for 20 values and its duration is 1 hour and 15 minutes.
The classification of the theoretical-practical component corresponds to the arithmetic mean of the classifications obtained in the two written tests and has a weight of 80% in the final grade.
The classification of the practical component has a weighting of 20% in the final grade and corresponds to the classification of a teamwork
A student will be considered approved to this curricular unit and excluded from the complementary evaluation or final examination evaluation if the classification in each one of the written tests is at least 6.5 and the final classification is at least 9.5 values, according to the following formula:
Final Classification = 0.2*NTrG+0.4*NT1+0.4*NT2,
where NTrG represents the classifications of the practical teamwork and NTi represents the classification obtained in Test i, with i = 1,2.
The complementary assessment (Mode 2) allows the repetition of one of the tests of Mode 1, on the 1st date of the exam. The duration of the test is 1 hour and 15 minutes. The final grade will be computed as described in the continuous assessment, where the classification of the complementary test will replace the classification of the corresponding test in the continuous assessment.
If the students intend to perform the complementary assessment, they should make their registration in the appropriate location on the SIDE (Complementary Assessment 1st test or Complementary Assessment 2nd test), indicating thereby the test they want to repeat.
The students that have been admitted to the complementary assessment and did not appear to the test or, having appeared, have given up or have been not approved, are admitted to the 2nd exam.
The final assessment (Mode 3) consists of written and/or oral examinations, each one with a theoretical-practical component in which all the syllabus contents explored in the classes is under assessment.
Each theoretical-practical test is rated for 20 points and lasts for 2 hours and 30 minutes. This exam will have a contribution of 80% in the final result, while the other 20% corresponds to teamwork.
A student will be considered approved in this course unit if he obtains in the exam a final grade greater than or equal to 9.5 points.
The students with a final grade in the range [8.5,9.5[ may be submitted to an additional examination (oral or written), if they wish. They obtain approval to the course unit if the average of the classifications obtained in the written and additional examinations is greater than or equal to 9.5.
In either assessment modes, the students that obtained a classification greater than or equal to 16.5 points, and are seeking for a final grade higher than 16, will have to validate the classification with an additional examination. The final grade is the classification of the additional examination (or 16, if the classification of the additional examination is less than 16).
The students regularly enrolled in the UC and that meet the conditions described in the Pedagogical Regulation have access to the special (3rd) exam.
To have access to the exam, the students need to enroll in the Academic Services, as well as in the SIDE.
The exam consists of a theoretical-practical component rated for 20 points and lasts for 2 hours and 30 minutes.
In any written examination,
(a) the students must have an identification document beyond the UTAD's student card;
(b) is not allowed to consult any notes and/or books;
(c) is allowed to use a non-alphanumeric/non-programmable calculator;
(d) is not allowed to use pencil and corrector pen in the test sheet;
(e) the students can not leave the room, in any case, during the time of the examination;
(f) a student wishing to give up must declare it, in writing, on the test sheet, and can only leave the examination room after permission of the teacher and not earlier than 30 minutes after its start;
(g) is allowed the examination to students that arrive at the room until 20 minutes after the examination starts. The student who is granted this permission does not have, for that reason, extra time to finish the examination;
(h) is not allowed all the communication between students that, directly or indirectly, allow to obtain or collect information about the content of the exam and also is not allowed to use mobile phones or other communications and recording equipment;
(i) fraud or plagiarism implies the annulment of the examination and can bring to the student disciplinary action.
Minimum criteria for admission to examination
A minimum condition of admission to access the assessment and/or examination is to assist a minimum of 70% of the contact hours (theoretical-practical classes), except students with special statutes or students that satisfied the admission conditions in the academic year 2018-19.
Description of evaluation methods, respecting the Article 13 of Chapter IV of UTAD's Pedagogical Regulation (including, scheduling and calculation method).
Dates of the tests:
1st test - November 15, 2019.
2nd test - January 10, 2020.
Continuous assessment to be carried out during the semester will consist of 2 written tests (PE1 and PE2), with a weighting of 80% in the final grade, and a group practical work, with a weighting of 20% in the final grade. Each of the written tests will be graded for 20 values, and its duration will be 1h15min.
The classification of the practical component corresponds to the classification of the group practical work. The oral presentation of work is mandatory for all the elements of the group.
A student will be considered approved to this curricular unit and exempted of complementary evaluation or final examination evaluation if the classification in each one of the written tests is at least 6.5 and the final classification (based on practical and theoretical-practical components) is at least 9.5 values, according to the following formula:
Final Classification = 0.2 * NTrG + 0.4 * NT1 + 0.4 * NT2,
Where NTrG represents the classification of the practical works and NTi represents the classification obtained in Test i, with i = 1,2.
The supplementary assessment (Mode 2) enables to repeat one of the written tests provided for in Mode 1 on the normal examination date. The final classification will be calculated as described in the continuous evaluation, where the grade obtained in the complementary assessment test will replace the grade of the corresponding continuous assessment.
May submit to evaluation mode 3, all the students who fulfill the minimum criteria for admission to examination listed in this Curricular Unit form. This evaluation is constituted by a Final Examination (EF) worth 20 values and with 2h 30m of duration, being the entire syllabus in the UC object of evaluation, and will have an 80% contribution to the final classification.
The final classification (CF) will be CF= 0.8*EF + 0.2*NTrG.
Will be approved to the curricular unit the students with final grade (CF) not less than 9.5. However, if the students obtain a final classification (CF) in the interval [8.5, 9.5 [, they will be able to make an extra exam, being approved to the curricular unit if the final average rating CF together with the classification of the extra exam is not less than 9.5.
Cerveira, A., Nascimento, M.
Introduction to Operations Research
Hillier, F. S.; Lieberman, G.J.
Investigação Operacional Vol. 1 Programação Linear
Manuela Magalhães Hill, Mariana Marques dos Santos
Investigação Operacional Vol. 3 Transportes, Afectação e Optimização em Redes
Manuela Magalhães Hill, Mariana Marques dos Santos, Ana Líbano Monteiro
Linear and Nonlinear Optimization
Griva, I., Nash, S., Sofer, A.
Network Flows: Theory, Algorithms and Applications