Público: Alunos de Graduação em Ciência da Computação, Matemática Computacional, e Engenharias, interessados em modelar e resolver problemas de Otimização.
Pré-requisitos: Geometria Analítica e Álgebra Linear, Programação de computadores em nível equivalente a PDS1, conhecimento de linguagem Python. Não é necessária formação prévia em Otimização.
Ementa: Classes de problemas de Otimização. Problemas de Programação Matemática. Pacotes de otimização linear, linear inteira e não linear. Problemas de Otimização Combinatória. Conceito de formulação. Conceitos básicos de Teoria dos Grafos. Problemas de Programação Linear, Programação Linear Inteira. Conceitos básicos para algoritmos em programação linear inteira: relaxações e enumeração implícita (Branch-and-bound). Técnicas básicas de modelagem. Modelagem de problemas de otimização combinatória que envolvem: conexidade, dominância, coloração, resiliência, etc.
Objetivos: Este curso visa apresentar uma introdução à modelagem de problemas de otimização, com foco em otimização combinatória. A ideia é apresentar diversos problemas de otimização combinatória, suas aplicações e discutir modelos de Programação Matemática distintos para tais problemas. Na sequência, estes modelos serão implementados em linguagem Python e serão resolvidos com algoritmos (pacotes de otimização) previamente disponibilizados. O objetivo não é investigar em detalhes os algoritmos empregados para se resolver estes problemas. Apenas as ideias centrais de alguns destes algoritmos serão apresentadas no curso, o suficiente para o uso confortável de pacotes de otimização, e para resolvermos os modelos que iremos obter e para interpretarmos as soluções encontradas. O objetivo central é discutir como modelar. Via de regra, vamos discutir mais de uma, várias formulações distintas para cada problema, paradigmas distintos de modelagem, destacando vantagens e desvantagens de cada uma. Além disso, vamos discutir implicações algorítmicas de cada formulação.
Problemas de Otimização Combinatória que serão modelados e resolvidos:
- Problemas básicos de conexão em grafos.
- Problema de Steiner em Grafos e variantes.
- Projeto de redes de comunicação resilientes.
- Problemas de Interdição em redes.
- Problema do Caixeiro Viajante e variantes.
- Problemas de estruturas induzidas em grafos.
- Problema de Roteamento de Veículos.
- Problema de Coloração em Grafos.
- Problema de Dominância e Dominância Conexa em Grafos.
- Problemas de Agrupamento e de Clusterização.
- Problema do Corte Máximo.
- Problemas de Sequenciamento de Atividades/Máquinas.
- Cutting-stock (problemas de definir padrões ótimos de cortes)
- Problemas de empacotamento.
Referências bibliográficas principais:
- Biblioteca Pyomo para Python: http://www.pyomo.org/
- Michael L. Bynum, Gabriel A. Hackebeil, W. E. Hart, Carl. D. Laird, Bethatny L. Nicholson, J. D. Siirola, Jean-Paul Watson, David L. Woodruff, Pyomo – Optimization Modeling in Python, 3a Edição, 2021, Springer.
- H. Paul Williams, Model Building in Mathematical Programming, 5a Edição, 2013, Wiley.
- J. A. Bondy e U. S. R. Murty, Graph Theory, 2010, Springer.
- Laurence Wolsey, Integer Programming, Wiley, 1998.
- Christos H. Papadimitriou e Kenneth Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover, 1998.
- Marco Cesar Goldbarg e Henrique Pacca Luna, Otimização Combinatória e Programação Linear, Editora Campus, 2000.
- Artigos selecionados pelo professor para apresentação de modelos para cada um dos problemas identificados acima.
Forma de avaliação:
- Listas de exercícios de modelagem (30 pontos).
- 1 mini-projeto (20 pontos). Trata-se de um pequeno ensaio para o projeto principal.
Os temas deste mini-projeto serão os mesmos para toda a turma. - Desenvolvimento de um projeto principal individual (50 pontos) na forma de um artigo, com a orientação do professor, em tema escolhido pelo aluno em conjunto com o professor. Possivelmente este tema será uma variação de algum dos problemas descritos acima.
Prof. Alexandre Salles da Cunha
Departamento de Ciência da Computação
Universidade Federal de Minas Gerais