Resumo: Para colocar em produção novos poços de petróleo e gás ou realizar a manutenção dos existentes, são necessárias sondas e barcos de carregamento de linha. Esse recursos são escassos devido a seu custo e extremamente requisitados. Além disso, precisam passar por períodos de manutenção planejada e atender a diversas restrições operacionais para realizar cada tipo de atividade prevista. Nos primeiros 20 minutos, será apresentado o material levado em junho ao ALIO-Informs Joint International Meeting em Buenos Aires (http://meetings2.informs.org/BuenosAires2010/index.html). Esse material consiste na descrição do problema, revisão de abordagens anteriores para resolvê-lo, relato da experiência em aplicar programação por restrições nessa abordagem e alguns resultados preliminares do sistema que será utilizado na Petrobras. De acordo com o andamento da apresentação, esse material pode ser complementado com uma descrição teórica mais detalhada da técnica de programação por restrições.

Resumo: Um problema bastante conhecido é o de escolher uma rota para se fazer uma viagem, tal que a rota minimize a distância do percurso. Nesta forma básica, esse problema é o problema de caminho mínimo em grafos onde as arestas são possíveis trechos, valorados por seu comprimento. Algumas vezes um caminho mínimo desta forma é bom, outras vezes não. Existem ocasiões, onde tal caminho possui propriedades indesejáveis. Por exemplo, alguns trechos podem ter tráfego denso e nos fazer perder muito tempo na travessia, ou existem muitos pedágios com taxas que, acumuladas pelo caminho, vão exceder o dinheiro que temos disponível. Isso nos leva a considerar um ou mais parâmetros adicionais para a escolha do caminho. Os casos mais comuns de parâmetros a considerar envolvem o consumo de recursos em um orçamento que limita a quantidade disponível desses recursos. Um caminho mínimo com essas limitações adicionais é chamado de Caminho Mínimo com Recursos Limitados (resource constrained shortest path - RCSP). A adição da restrição a um único recurso já é suficiente para tornar o problema tão difícil quanto problemas da classe NP-Difícil. Uma abordagem para o problema é utilizar um algoritmo de K-Menor Caminho (k-shortest path), terminando com o primeiro caminho que satisfaz as restrições. Esta técnica é impraticável quando o valor de K é muito grande. Handler e Zang propuseram um método, usando relaxação lagrangeana, que foi projetado para reduzir este valor de K. Resultados computacionais indicam uma redução bastante considerável da magnitude de K com a utilização desta técnica. Neste seminário pretendemos falar de forma detalhada sobre o algoritmo proposto por Handler e Zang.

Resumo: Uma coloração de vértices de um grafo é chamada convexa se, para cada cor, o subgrafo induzido pelos vértices com essa cor é conexo. O problema da recoloração convexa de grafos consiste em, para um dado grafo colorido, fazer o menor número possível de alterações de cor, de modo a obter uma coloração convexa. Uma tal recoloração é chamada ótima. Este problema possui aplicações em diversas áreas, tendo os primeiros resultados surgidos em 2005 para o caso especial de árvores filogenéticas. Para o caso especial em que a árvore é um caminho o problema foi provado ser NP-difícil por Moran e Snir. Para este caso é conhecido um algoritmo (polinomial) que é uma 2-aproximação. Ainda para o caso especial deste problema sobre caminhos, nos quais cada cor ocorre no máximo duas vezes (2-PRCC), o problema também foi provado ser NP-difícil. Neste seminário, apresentaremos a prova de que 2-PRCC é NP-difícil e mostraremos um algoritmo que é uma 3/2-aproximação.

Resumo:

Resumo:

Resumo:

Resumo:

Resumo: