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
54
Língua de ensino
Português
Objectivos
Esta UC está focada no estudo de problemas combinatórios (de satisfação e/ou optimização), nomeadamente na sua modelação e métodos de resolução. É adoptado um paradigma de programação declarativo, em que a declaração das restrições é especificada separadamente da sua resolução. A resolução destes problemas pode ser abordada de duas perspectivas alternativas ou complementares: a) pesquisa completa, com retrocesso, oferecendo garantias de completude mas com limitações na dimensão dos problemas abordados; b) pesquisa local, que não oferecendo essas garantias permite uma resolução (aproximada) de problemas de maior dimensão.
Nesta UC, pretende-se que os alunos obtenha conhecimento e experiência significativos na modelação e resolução destes problemas, permitindo-lhes identificar para um dado problema, a) quais os melhores modelos a adoptar na sua especificação, b) quais os método de resolução mais adequados às características do problema, e c) quais as limitações inerentes à natureza combinatória do problema.
Conteúdo
1. Problemas de Decisão e Otimização
- Modelação declarativa de restrições
- Tipos de restrições: tabeladas, aritméticas, disjuntivas, reificadas, globais
- Complexidade.
2. Métodos Completa de Resolução / Retrocesso
- Redes de restrições
- Consistências locais (nó, arco, domínio/limites)
- Consistências não-locais (caminho, k)
- Algoritmos para a sua manutenção
- Heurísticas para Pesquisa
- Seleção de variável e valor
- Heurísticas genéricas (dom, deg, dom/wdeg, impact)
- Otimização - Branch & Bound
3. Resolução Incompleta de Restrições - Pesquisa Local Restringida
- Invariantes e objetos diferenciáveis
- Grau de satisfação de restrições
- Heurísticas
- Baseadas em variáveis ou em restrições
- Ávidas e estocásticas
- Meta-heurísticas
- Recomeços, tabu, Arrefecimento simulado
- Vizinhanças grande e variável
- Colónias de formigas
Bibliografia
Livros de Texto:
• Dina Rechter, Constraint Processing, Morgan Kauffman, 2003.
• Pascal Van Hentenryck and Laurent Michel, Constraint-Based Local Search, MIT Press, 2009.
Manuais:
• Comet Tutorial, Dynamic Decision Technologies Inc., August 28, 2009
Leituras Adicionais:
• Handbook of Constraint Programming, F. Rossi, P. van Beek & T. Walsh (eds), Elsevier Science, 2008
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. O alunos deverão ter um mínimo de 6 valores, quer na média dos testes/exame, quer na média dos projectos.
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 6 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 (21 Outubro a 9 Novembro)
Mini-Teste_1 – Conceitos de Programação por Restrições (31 Outubro)
Trabalho_2 – Problema de Pesquisa Local Restringida (25 Novembro a 14 Dezembro)
Mini-Teste_2 – Conceitos de Pesquisa Local Restringida (12 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 (data a anunciar)