Optimization

Code:

2MADSAD03

Acronym:

O

Keywords
Classification	Keyword
OFICIAL	Management Studies

Instance: 2018/2019 - 1S

Active?	Yes
Responsible unit:	Management
Course/CS Responsible:	Master in Modeling, Data Analysis and Decision Support Systems

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
MADSAD	27	Bologna Official Syllabus	1	-	7,5	56	202,5

Teaching language

English

Objectives

• 
  

  Provide an introduction to combinatorial optimization problems, and distinguish between exact and heuristic methods.

  
  


• 
  

  Describe the main concepts regarding dynamic programming, deterministic and stochastic.

  
  


• 
  

  Describe the main concepts regarding constructive heuristics.

  
  


• 
  

  Describe the main concepts regarding neighbourhood and local search.

  
  


• 
  

  Describe the main concepts regarding metaheuristics.

  
  


• 
  

  Describe the basic versions of the Simulated Annealing, Tabu Search and Genetic Algorithm metaheuristics.

  
  

Learning outcomes and competences

After completing this course unit, the student should be able to:

• Formulate a problem using a dynamic programming model (deterministic or stochastic).

• Use the MATLAB software to implement and solve a deterministic dynamic programming model.

• Propose a constructive heuristic for a combinatorial optimization problem.

• Propose a neighbourhood for a combinatorial optimization problem.

• Describe the main concepts regarding metaheuristics, including the concepts of diversification and intensification.

• Describe the main components of the Simulated Annealing, Tabu Search and Genetic Algorithms metaheuristics.

• Establish relations and propose synergies between metaheuristics.

Working method

Presencial

Program

• 
  

  Introduction to Combinatorial Optimization

  
  


• 
  

  Exact Methods

  
  




• 
  

  Deterministic Dynamic Programming

  
  


• 
  

  Stochastic Dynamic Programming

  
  




• 
  

  Heuristic Methods

  
  




• 
  

  Constructive Heuristics

  
  


• 
  

  Neighbourhood

  
  


• 
  

  Local Search

  
  


• 
  

  Introduction to Metaheuristics

  
  


• 
  

  Simulated Annealing

  
  


• 
  

  Tabu Search

  
  


• 
  

  Genetic Algorithms

  
  

Mandatory literature

Gendreau Michel 340; Handbook of metaheuristics. ISBN: 978-1-4419-1663-1
Bertsekas Dimitri P. 1942-; Dynamic programming and optimal control. ISBN: 1-886529-08-6 Set

Teaching methods and learning activities

• 
  

  Theoretical exposition.

  
  


• 
  

  Illustrative examples.

  
  

Software

MATLAB
Microsoft Excel

Evaluation Type

Distributed evaluation without final exam

Assessment Components

Designation	Weight (%)
Teste	50,00
Trabalho escrito	50,00
Total:	100,00

Amount of time allocated to each course unit

Designation	Time (hours)
Estudo autónomo	46,50
Trabalho escrito	100,00
Total:	146,50

Eligibility for exams

All students enrolled in the course may take the final exam.

Calculation formula of final grade

Regular Examination Period

In the regular examination period the only assessment type is distributed assessment. Thus, there is no evaluation via final exam only.

The distributed assessment consists of:

• Group assignment(s) regarding Exact Methods. Weight in the final grade: 25%.

• TGroup assignment(s) regarding Heuristic Methods. Weight in the final grade: 25%.

• Final test. Weight in the final grade: 50%.

All assignments and the test are required to pass the course via distributed assessment. Therefore, a student cannot pass the course, via distributed assessment, if she / he fails to do the test, or any of the assignments.

There is a minimum score of 6.0 in the final test, as well as on each assignment. Therefore, if a student scores lower than 6.0 on the test, or on any of the assignments, she / he will fail the course, regardless of the overall weighted score.

Reassessment Examination Period

In the reassessment examination period the only assessment type is final exam.

If a student did all the distributed assessment assignments, the score of those assignment will be taken into account to calculate the final grade, if it improves that final grade. In this case, the final grade will be calculated in the same way as in the distributed assessment (the exam will replace the final test). If the score of the assignments does not improve the final grade, the final grade will be equal to the score of the exam.

Classification improvement

A student who passes the course via final exam may only improve her / his grade via final exam. A student who passes the course, in the regular examination period, via distributed assessment, may improve the score of the regular examination period test by taking the final exam in the immediatly subsequent reassessment examination period. The grades of the assignments cannot be improved.