Optimization

Code:

2MADSAD03

Acronym:

O

Keywords
Classification	Keyword
OFICIAL	Management Studies

Instance: 2019/2020 - 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	38	Bologna Official Syllabus	1	-	7,5	56	202,5

Teaching language

English

Objectives

Objectives:

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

• Describe the main concepts regarding integer linear programming.

• Describe the main concepts regarding the Branch-and-Bound method.

• 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 an integer linear programming model.

• Use Excel to solve an integer linear programming model using the Branch-and-Bound method.

• 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

Programme:

• Introduction to Combinatorial Optimization

• Exact Methods

• Integer Linear Programming

• The Branch-and-Bound Method

• 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
Nemhauser, George L.; Wolsey, Laurence A.; Integer and Combinatorial Optimization, Wiley

Teaching methods and learning activities

Teaching methods and learning activities:

• Theoretical exposition.

• Illustrative examples.

Software

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: 20%.

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

• 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 immediately subsequent reassessment examination period. The grades of the assignments cannot be improved.