Pesquisa e Otimização
Código
10799
Unidade Orgânica
Faculdade de Ciências e Tecnologia
Departamento
Departamento de Informática
Créditos
6.0
Professor responsável
Pedro Manuel Corrêa Calvente Barahona
Horas semanais
4
Total de horas
58
Língua de ensino
Português
Objectivos
Saber:
- Problemas de satisfação de restrições e de optimização.
- Tipos de restrições (simples / globais).
- Propagação de restrições e tipos de consistência.
- Algoritmos completos e incompletos para satisfação/optimização.
- Heurísticas e meta-heurísticas.
Saber Fazer:
- Modelação de problemas de satisfação/optimização de restrições.
- Escolha das restrições mais adequadas.
- Escolha dos algoritmos mais apropriados.
- Escolha das heurísticas mais eficientes.
Competências Complementares:
- Compreensão de especificações informais (eventualmente incompletas).
- Identificação de problemas de restrições.
- Análise e explicação de resultados.
- Capacidade de pesquisa de literatura.
Pré-requisitos
Um conhecimento básico de programação e de pesquisa combinatória.
Conteúdo
- Problemas de Decisão e Otimização.
1. Problemas de Decisão e Otimização.
1.1. Exemplos.
1.2. Complexidade.
1.2.1. Resolução Completa de Restrições - Pesquisa com Retrocesso.
2.1. Tipos de restrições.
2.1.1. Aritméticas.
2.1.2. Disjuntivas.
2.1.3. Reificadas.
2.1.4. Globais.
2.2. Redes de restrições
2.2.1. Consistências locais (nó, arco, domínio/limites).
2.2.2. Consistências não-locais (caminho, k).
2.2.3. Algoritmos para a sua manutenção.
2.3. Heurísticas para Pesquisa.
2.3.1. Seleção de variável e valor.
2.3.2. Heurísticas genéricas (dom, deg, dom/wdeg, impact).
2.3.3. Optimização - Branch & Bound
- Resolução Incompleta de Restrições - Pesquisa Local Restringida.
3.1.Modelação declarativa de restrições.
3.1.1. Invariantes e objetos diferenciáveis.
3.1.2. Grau de satisfação de restrições.
3.2. Heurísticas
3.2.1. Baseadas em variáveis ou em restrições.
3.2.2. Ávidas e estocásticas.
3.3.Meta-heurísticas
3.3.1. Recomeços.
3.3.2. Pesquisa tabu.
3.3.3. Arrefecimento simulado.
3.3.4. Pesquisa com vizinhança variável.
3.3.5. Colónias de formigas.
Bibliografia
Livros de Texto
- Dina Rechter, Constraint Processing, Morgan Kauffman, 2003.
- Constraint-Based Local Search, MIT Press, 2005.
Manuais
Comet Tutorial, Dynamic Decision Technologies Inc., August 28, 2009
Método de ensino
O programa é leccionado em aulas teóricas e práticas. Nas primeiras são leccionados os conceitos e técnicas relevantes bem como a forma como estão implementados na linguagem e sistema de modelação e resolução utilizada (Comet).
Nas aulas práticas são resolvidos problemas retirados de uma biblioteca especializada (CSPLIB), sendo explorados modelos e técnicas de pesquisa alternativas disponibilizadas em Comet.
Método de avaliação
A avaliação (contínua) integra 4 componentes: 2 trabalhos e 2 mini-testes, todos avaliados na escala de 0-20, e com o mesmo peso de 25% para a nota final.
Os trabalhos são feitos em grupos (de 2 alunos) e os mini-testes avaliam os alunos individualmente. Os alunos que não tiverem uma nota mínima de 10 valores são admitidos a exame de recurso, se tiverem frequência (pelo menos 8 valores na média dos trabalhos de grupo).
Os componentes de avaliação cobrem os seguintes tópicos:
- Trabalho_1 – Problema de Programação por Restrições (18 Out - 1 Nov)
- Mini-Teste_1 – Conceitos de Programação por Restrições (2 Novembro)
- Trabalho_2 – Problema de Pesquisa Local Restringida (10 Dez - 30 Dez)
- Mini-Teste_2 – Conceitos de Pesquisa Local Restringida (22 Dezembro)
As notas obtidas no exame final substituem as obtidas nos 2 mini-testes (se melhores.
- Exame – Conceitos de Programação por Restrições e de Pesquisa Local Restringida (9 Jan)