Universidade Federal do Espírito Santo
Laboratório de Otimização
LabOtim
http://labotim.inf.ufes.br
sala 10 do CT VII
Coordenação:
Maria Cristina Rangel ([email protected])
Departamento de Informática - DI
Programa de Pós-Graduação em Informática – PPGI
13/04/2011
Pesquisas em Otimização
Combinatória e Pesquisa Operacional
• Desenvolvimento de modelos de logística e otimização para o
setor produtivo;
• Estudos teóricos para problemas em Teoria dos Grafos;
• Heurísticas e metaheurísticas para problemas modelados em
Otimização Combinatória;
• Aplicações em Fluxos em Redes;
• Computação Científica Combinatorial.
Professores atualmente ligados
ao laboratório
• Arlindo Gomes de Alvarenga (DI/PPGI/UFES)
• Hannu Tapio (PPGI/UFES)
• Lucia Catabriga (DI/PPGI/UFES)
• Maria Claudia Silva Boeres (DI/PPGI/UFES)
• Maria Cristina Rangel (DI/PPGI/UFES)
• Renato Antônio Krohling (PPGI/UFES)
Alunos atualmente ligados
ao laboratório
• 10 alunos de mestrado
• 5 alunos de graduação
– iniciação científica
– projeto final de graduação
Projetos já realizados no LabOtim
• Título: Problemas de Cobertura, Empacotamento e
Partição de um Conjunto
Início: outubro/2000
Financiamento: CNPq
Coordenador: André Renato Sales Amaral (Coordenador)
• Título: Técnicas Avançadas para Problemas de Cobertura,
Empacotamento e Partição de um Conjunto
Início: Junho/2001
Financiamento: CNPq
Coordenador: André Renato Sales Amaral
Alunos: Alexandre Clark Franco, Terence Amorim Fiedler,
Lorena Zancheta
Projetos já realizados no LabOtim
• Título: Resolução do Problema de Partição de um
Conjunto no Contexto da Computação Paralela de
Métodos de Elementos Finitos
Início: Julho/ 2003
Financiamento: CTpetro/CNPq
Coordenador: André Renato Sales Amaral
Alunos: André Camatta, Renzo Zamprogno, Fabbiano
Ferrari, Thiago Lourenço
• Título: Transporte Escolar Rural no Âmbito da SEDU/IPES
Início: junho/2004
Financiamento: SEDU
Coordenadores: Arlindo Gomes de Alvarenga
Hannu Tapio Ahonen
Projetos já realizados no LabOtim
• Título: O estudo do Problema de Correspondência de Grafos
Aplicado À Detecção de similaridades entre mapas
conceitua
Início: Agosto/ 2005
Financiamento: Fundação de Amparo à Pesquisa do Espírito
Santo (FAPES)
Coordenadora: Maria Claudia Silva Boeres
Equipe: Davidson Cury e Crediné Silva de Menezes
alunos: Flávio Lamas, Guilherme Carlesso
• Título: Estudo de Problemas de Otimização em Logística
Ferroviária
Início: março/2007
Financiamento: sem financiamento
Cadastrado na PRPPG/UFES
Coordenadora: Maria Claudia Silva Boeres
Alunos: Rodrigo Alves Sarmento e Nhemias Basto
Projetos recentes no LabOtim
• Título: Fortalecimento das Áreas de Computação de Alto
Desempenho, Otimização e Inteligência Computacional do
Programa de Pós-Graduação em Informática da UFES
Início: dez/2008
Financiamento: CNPq – Edital do Projeto Casadinho
Coordenador: Alberto Ferreira De Souza (LCAD)
Participação de grande equipe do PPGI unida com
COPPE/UFRJ
• Título: Núcleo de Excelência em Computação de Alto
Desempenho e sua Aplicação em Computação Científica e
Inteligência Computacional
Início: dez/2010
Financiamento: CNPq/FAPES – EDITAL PRONEX 2009
Coordenador: Alberto Ferreira De Souza (LCAD)
Participação de grande equipe do PPGI unida com
COPPE/UFRJ
Dissertações de mestrado
defendidas e em andamento
•
Título: Uma Abordagem do Problema de Programação de
Grade Horária Sujeita a Restrições Utilizando Coloração
de Grafos
Aluno: Geraldo Simonetti Bello
Início: março/2005 – Defesa: março/2007
Orientadores: Maria Claudia Silva Boeres e Maria Cristina Rangel
•
Título: Resolução do Problema de Isomorfismo de Grafos
como um Problema Quadrático de Alocação
Aluno: Luciana Lee (Petrobras)
Início: março/2005 – Defesa: agosto/2007
Orientadores: Maria Cristina Rangel e Maria Claudia Silva Boeres
Dissertações de mestrado
defendidas e em andamento
•
Título: O estudo do problema de blocagem de vagões de
trens
Aluno: Rodrigo Alves Sarmento (FAPES)
Início: março/2007 – Defesa: agosto/2009
Orientadores: Maria Claudia Silva Boeres e Anilton Sales Garcia
•
Título: Programação em Dois Níveis: Teoria e Algoritmos
Aluno: Leonardo Delarmelina Secchin (CAPES)
Início: março/2008 – Defesa: março/2010
Orientadores: Arlindo Gomes de Alvarenga e Hannu Tapio
Dissertações de mestrado
defendidas e em andamento
Título: Teoria Espectral de Grafos aplicada ao Problema de
Isomorfismo de Grafos
Início: março/2008 – Defesa: agosto/2010
Aluno: Philippe Leal (FAPES)
Orientadoras: Maria Cristina Rangel e Maria Claudia Silva Boeres
• Título: Algoritmo Heurístico para Partição de Grafos com
Aplicação em Processamento Paralelo
Início: março/2008 – Defesa: agosto/2010
Aluno: Renato Stocco Bonatto (CAPES)
Orientador: André Renato Sales Amaral
Dissertações de mestrado
defendidas e em andamento
• Título: Abordagens baseadas em Teoria Espectral de Grafos
para o Problema de Isomorfismo de Grafos
Início: março/2009
Aluno: Diego Barcelos Rodrigues (FAPES)
Orientadoras: Maria Cristina Rangel e Maria Claudia Silva Boeres
• Título: Estudo de Abordagens de Otimização Combinatória
para Simulações Numéricas com Matrizes Esparsas de Grande
Porte
Início: março/2009
Aluna: Kamila Ghidetti (Capes)
Orientadoras: Lucia Catabriga e Maria Claudia Silva Boeres
Dissertações de mestrado
defendidas e em andamento
• Título: Estudo de Algoritmos Paralelos para a Otimização da
Vazão em Poços de Petróleo
Início: março/2009
Aluno: João Olavo Baião de Vasconcelos (Petrobras)
Orientadoras: Maria Claudia Silva Boeres e Lucia Catabriga
Dissertações de mestrado
defendidas e em andamento
• Título: Estudo de um novo cenário de roteamento de tráfego
aplicado às redes ópticas
Início: março/2010
Aluno: Diego Luchi (FAPES)
Orientadora: Maria Cristina Rangel
• Título: Estudo da Teoria Espectral de Grafos aplicada à
Otimização Combinatória
Início: março/2010
Aluno: Marcos Daniel Valadão Baroni
Orientadoras: Maria Claudia Silva Boeres e Maria Cristina Rangel
Dissertações de mestrado
defendidas e em andamento
• Título: O Problema de Tabela Horário na Universidade –
Estudo de Caso: UFES
Início: março/2010
Aluno: Walace Rocha - NPD/UFES
Orientadoras: Maria Claudia Silva Boeres e Maria Cristina Rangel
• Título: O Estudo de Problema de Casamento Exato e Inexato
de Grafos
Início: março/2010
Aluno: Rômulo Douro
Orientadora: Maria Claudia Silva Boeres
Iniciações Científicas terminadas e
em andamento
• Título: Estudos de Métodos Heurísticos para Problemas de
Otimização Combinatórios Relacionados à Localização e
Transporte
Início: ago/2008
Aluno: Rodrigo Leione Passos – PIBIC/FACITEC – Engenharia
Ambiental
Orientadora: Maria Cristina Rangel
• Título: Avaliação de Matrizes Esparsas utilizando a Metaheurística GRASP
Início: ago/2009
Aluno: Thiago Moreira Molino – PIBIC/UFES – Engenharia Elétrica
Orientadora: Maria Cristina Rangel
Iniciações Científicas terminadas e
em andamento
• Título: Estudo do Problema do Caixeiro Viajante para
Simulações Numéricas com Matrizes Esparsas de Grande
Porte
Início: ago/2009
Aluno: Rafael Calmon Bermudes dos Santos (PIBIC/UFES) – Eng.
Computação
Orientadora: Maria Claudia Silva Boeres
• Título: Avaliação de Matrizes Derivativas advindas Método
de Newton utilizando Otimização Combinatória
Início: ago/2010
Aluno: Thiago Moreira Molino – PIBIC/UFES – Engenharia Elétrica
Orientadora: Maria Cristina Rangel
Iniciações Científicas terminadas e
em andamento
• Título: Avaliação de Matrizes Esparsas utilizando a Metaheurística TABU
Início: ago/2009
Aluno: Marcos Vinicius Batista S. de Lima (PIBIC/UFES) – Eng.
Computação
Orientadora: Maria Claudia Silva Boeres
• Título: Estudo de Heurísticas de Resolução do Problema do
Caixeiro Viajante Aplicado à Problemas de Simulações
Numéricas com Matrizes
Início: março/2010
Aluno: Marcos Vinicius Caus Couto (PET/Eng. Computação) voluntário
Orientadora: Maria Claudia Silva Boeres
Iniciações Científicas terminadas e
em andamento
• Título: Estudo de um AG para Resolução do problema de
Tabela-Horário
Início: março/2011
Aluno: Leandro B. Ferreira (Projeto Final de Graduação – CC)
Orientadora: Maria Claudia Silva Boeres
• Título: Estudo de Algoritmos de Busca Local
Início: março/2011
Aluno: Judismar Arpini
Orientadora: Maria Claudia Silva Boeres
O que é Otimização Combinatória?
• Problema Combinatório:
– Caracterizado por um conjunto de todos os possíveis
dados do problema (conjunto de dados) e por uma
questão solicitada (objetivo do problema).
– Resolver o problema consiste em desenvolver um
algoritmo cuja saída (solução) responda ao objetivo
do problema.
Alguns problemas de
Otimização Combinatória
•
•
•
•
Problema do Caixeiro Viajante
Problema de Coloração de Grafos
Problema de Isomorfismo de Grafos
Problema de Tabela Horário
O problema do Caixeiro Viajante
d
1
5
c
2
peso=16
4
2
a
abcda
6
b
abdca
peso=11
Otimização: localizar o melhor percurso
O problema de Coloração de Grafos
MG
BH
ES
RJ
SP
O problema de Isomorfismo de
Grafos
G1 =(V1 ,E1 )
G2 =(V2 ,E2 )
• Para serem isomorfos, os grafos devem ter mesmo número
de nós, arestas e sequência de graus.
• Definir uma função biunívoca f : V1 → V2 tal que
todo (a,b) em E1 → (f(a),f(b)) em E2
Métodos de Solução:
Heurísticas x Métodos Exatos
• Algoritmos exatos: encontram solução ótima
Simplex e Branch-and-bound
• O que é heurística?
HEURISKEIN = encontrar/descobrir
• Algoritmos heurísticos: técnicas que procuram boas
soluções com custo computacional razoável sem
garantia do ótimo e garantem a viabilidade
Exemplos de Algoritmos Heurísticos
• Multi-start
• GRASP (Greedy Randomized Adaptive Search
Procedure)
• Simulated Annealing
– Resfriamento do material até alcançar o equilíbrio
• Algoritmos Genéticos
– Evolução das Espécies: Melhores indivíduos sobrevivem
gerando filhos com suas características genética (otimização)
• Colônia de Formigas
– Baseia-se na busca por alimento de um formigueiro: Os
caminhos mais curtos são aqueles que a maioria das formigas
seguem (otimização)
Temas para Projetos de IC
• Estudo de algoritmos de caminhamento em grafos
(busca em largura, busca em profundidade, Best-First e
A*) e o impacto de escolha do vértice inicial no
desempenho desses algoritmos
• Estudo de algoritmos heurísticos para resolução do
problema de tabela-horário
• Estudo do Problema de Isomorfismo de Grafos e
implementação de um banco de dados
• Estudo do Problema de Roteamento dos Caminhões de
Coleta de Lixo
Obrigada!