OPTIMIZAçãO I
Código: 23028
ECTS: 10
Departamento: Departamento de Ciências e Tecnologia
Área Científica: Engenharia Informática
Palavras-Chave:
    Otimização
    Programação Linear
    Combinatória
    Meta-heuristícas
Docente:
Luís Cavique
Área Científica: Informática.
Correio Eletrónico: luis.cavique@uab.pt

Sinopse:
Esta UC visa proporcionar os conhecimentos e competências fundamentais acerca dos princípios, conceitos e técnicas das seguintes subáreas da Otimização: formulação em programação linear, otimização combinatória e determinação dos limites superiores e inferiores (heurísticas e relaxações).


Competências:
Ao concluir esta UC o estudante deverá estar capaz de:
  • Reconhecer o papel a importância da Otimização Combinatória no contexto mais geral da Otimização;
  • Identificar os principais métodos e técnicas de Otimização Combinatória para grandes volumes de dados;
  • Aplicar técnicas de Otimização em contexto experimental.


Conteúdos:
O programa desta UC consiste nos seguintes pontos:
1- Introdução
1.1- Formulação em Programação matemática, Problemas P e NP, Complexidade Algorítmica, Notação O;
1.2- Programação linear inteira, Enumeração implícita, Branch & Bound, Limites superiores e inferiores;
2- Problemas Combinatórios
2.1- Problema de Cobertura e relacionados: formulação, heurística construtiva e de melhoramentos;
2.2- Problema da Clique Máxima: formulação, heurística construtiva e heurísticas de melhoramentos;
3- Limites superiores e inferiores
3.1- Meta-heurísticas: apresentação das heurísticas de âmbito geral e diferentes taxionomias;
3.2- Relaxação Linear e Relaxação Lagrangeana.


Bibliografia:
• Luna & Goldbarg: Otimização combinatória e programação linear, Editora Campus, 2005;
• Nemhauser & Wolsey: Integer and Combinatorial Optimization, Wiley, 1999;
• Talbi: Metaheuristics: From Design to Implementation, Wiley, 2009.


Total de Horas de Trabalho: 260
Total de Horas de Contacto: 10

Avaliação:
A avaliação tem caráter individual e implica a coexistência de duas modalidades: avaliação contínua (60%) e avaliação final (40%). Essa avaliação será desenvolvida na aplicação de formas diversificadas, definidas no Contrato de Aprendizagem da unidade curricular.