Heurísticas para Problemas Combinatórios

Muitos problemas de enorme importância prática podem ser modelados como problemas de otimização combinatória. Isso inclui problemas complexos do mundo real das mais diversas áreas como, transporte, redes, logística, negócios, etc. Entre os métodos mais eficazes para resolver problemas de otimização combinatória encontram-se heurísticas e metaheurísticas. O objetivo deste curso é apresentar técnicas fundamentais e avançadas para a construção de heurísticas eficientes e sua aplicação a diversos problemas de otimização combinatória. Os alunos serão apresentados a uma variedade de técnicas, assim como ao desafio de aplicá-las a diferentes situações-problema.

Número de créditos: 4,0

Ementa:

• Revisão sobre teoria da complexidade.
• Problemas de otimização combinatória.
• Representação de soluções.
• Heurísticas construtivas.
• Busca local.
• Metaheurísticas: simulated annealing, busca tabu, iterated local search, greedy randomized adaptive search, variable neighborhood search, algoritmos genéticos e outros métodos populacionais.
• Aplicações.
• Tópicos sobre trabalhos experimentais com algoritmos.