Modelagem e Resolução de Problemas de Otimização Combinatória

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

Acesso por PERFIL

Pular para o conteúdo