1. Identification and allocation of the Curricular Unit

School

Escola de Ciências e Tecnologia

Department

Engenharias

Course code

5054

Course denomination

Mes. Int. em Engenharia Eletrotécnica e de Computadores

Curricular Unit code

12968

Curricular Unit denomination

Otimização e algoritmos

Teacher in charge

Name

Category

Maria Adelaide da Cruz Cerveira

Professor Auxiliar

Other teachers from Curricular Unit

Names

Categories

Maria Adelaide da Cruz Cerveira

Professor Auxiliar

2. General information

Teaching load / contact hours / ECTS

Autonomous work (hours)

Distribution of contact hours

Total (hours)

ECTS

48.00

OT

TP

3.00

30.00

81

3.00

Schedule of classes

1º semestre:

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

Begin

Duration

Location

From

To

Segunda, 14h00

02h30

F.121A

23/09/2019

18/01/2020

Quarta, 14h00

02h30

F.1.21A

23/09/2019

18/01/2020

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.

5. Bibliography

Recommended

Title

Author(s)

Programação linear

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