Heuristics and Metaheuristics

Code:

PRDEIG034

Acronym:

HM

Keywords
Classification	Keyword
OFICIAL	Mathematics

Instance: 2023/2024 - 1S

Active?	Yes
Web Page:	https://moodle.up.pt/course/view.php?id=2607
Responsible unit:	Department of Industrial Engineering and Management
Course/CS Responsible:	Doctoral Program in Engineering and Industrial Management

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
PRODEGI	3	Syllabus since 2015/16	1	-	6	42	162

Teaching language

English

Objectives

To give the first-year PhD students a broad, but simultaneously in-depth, overview of search and optimization methodologies, applicable to the resolution of multi-disciplinary decision problems, under a decision support framework.

Learning outcomes and competences

It is expected to endow the students with skills to:

- identify optimization problems and approach them in a structured way;

- define the most adequate abstraction level to model optimization problems for an algorithmic approach to their resolution.

- identify the algorithmic techniques to solve a particular optimization problem;

- use heuristics and metaheuristics methods to obtain solutions for the problems;

- implement, test and validate, search methodologies to solve different classes of optimization problems.

 

Working method

Presencial

Pre-requirements (prior knowledge) and co-requirements (common knowledge)

Previous knowledge on Methodology of Operations Research and on programming languages.

Program

Heuristics and Local Search

Constructive heuristics

Exhaustive search

Neighbourhood structures

Local search

Divide and Conquer and Dynamic Programming

Branch and Bound and A* Algorithms

Dealing with infeasibility in search methods

Non-populational metaheuristics

- Simulated Annealing

- Tabu Search

- GRASP

- Variable Neighbourhood Search

- Other non-populational metaheuristics

Populational metaheuristics

- Genetic algorithms and evolutionary programming

- Ant Colonies

- Other populational metaheuristics

 

Mandatory literature

Michaelwicz, Zbigniew; Fogel, David B; How to Solve It: Modern Heuristics, Springer-Verlag, 2004. ISBN: 3-540-22494-7
El-Ghazali Talbi; Metaheuristics. ISBN: 978-0-470-27858-1

Complementary Bibliography

ed. by Edmund K. Burke, Graham Kendall; Search Methodologies. ISBN: 978-0387-23460-1
ed. Colin R. Reeves; Modern heuristic techniques for combinatorial problems. ISBN: 0-07-709239-2
Frederick S. Hillier, Gerald J. Lieberman; Introduction to operations research. ISBN: 007-123828-X

Teaching methods and learning activities

Classes will be mainly organized as lectures, in opposition to home work that will mainly be organized around assignments and therefore will take place in off class periods.
A strong interaction and participation of students, leading to a real active learning environment, will be sought in the lectures. In concrete the following learning strategies will be used:
- Group discussion based on scientific papers
- Small problems discussion and resolution
- Exploitation of alternative problem development paths
- Resolution of an optimization project

keywords

Physical sciences > Mathematics > Applied mathematics > Operations research
Physical sciences > Mathematics > Algorithms

Evaluation Type

Distributed evaluation with final exam

Assessment Components

Designation	Weight (%)
Trabalho escrito	30,00
Trabalho laboratorial	70,00
Total:	100,00

Amount of time allocated to each course unit

Designation	Time (hours)
Estudo autónomo	36,00
Frequência das aulas	42,00
Trabalho laboratorial	84,00
Total:	162,00

Eligibility for exams

N/A

Calculation formula of final grade

The components for student evaluation are:

- Individual work assignment on the preparation of a scientific paper that reports the implementation of a neighborhood-based search to a standard combinatorial optimization problem (weight of 50%)

- Group work (weight of 50%), about the implementation of a population or neighborhood-based search heuristc to address an optimization problem within the scope of the PhD project of the student.

Each component will be graded and the final score will be calculated as the weighted average of all components.

  

Examinations or Special Assignments

N/A

Special assessment (TE, DA, ...)

These students will be subject to all evaluation procedures of regular students, i.e., they must deliver their assignments specified during the course plus any special works also specified, being the only difference towards regular students that they are not required to attend classes and deliver assignments in the same dates as regular students, in the cases the law specifically states it.

Classification improvement

N/A