Técnicas Avançadas para Problemas de Cobertura, Empacotamento e Partição de Um Conjunto

Resumo: Problemas de cobertura, empacotamento e partição de um conjunto apresentam modelos de programação inteira com estrutura bastante peculiar. Estes problemas possuem grande importância prática e teórica.Considera-se um conjunto S de objetos e uma classe T de subconjuntos de S. Cada subconjunto de S possui um custo associado. O Problema de Cobertura de um Conjunto é como cobrir todos os objetos de S com mínimo custo, utilizando-se apenas membros de T. No Problema de Empacotamento, cada subconjunto de S possui um valor associado. Deseja-se empacotar em S a maior quantidade possível de membros de T para maximizar o valor total, mas sem causar sobreposição. O Problema de Partição de um Conjunto pode ocorrer no contexto de maximização ou minimização. O objetivo é tomar membros de T para construir uma partição do conjunto S de máximo valor total (ou de mínimo custo). Os métodos de combinatória poliédrica têm se mostrado adequados para uma enorme faixa de problemas de otimização combinatória. Associa-se ao problema um politopo cujos vértices são as soluções viáveis do problema.Estuda-se a estrutura deste politopo a fim de obter assim uma boa descrição parcial. Desenvolvem-se algoritmos para os problemas de separação das classes de facetas conhecidas. Tais facetas podem ser incorporadas em um algoritmo Branch-and-Cut para o problema. Aplicações mais gerais de cobertura, empacotamento ou partição requerem o atendimento de restrições extras. Neste caso, é suficiente adicionar tais restrições ao programa inteiro para obter-se a formulação correta.

Data de início: 2001-06-01
Prazo (meses): 12

Participantes:

Papel Nomeordem decrescente
Coordenador André Renato Sales Amaral
Acesso à informação
Transparência Pública

© 2013 Universidade Federal do Espírito Santo. Todos os direitos reservados.
Av. Fernando Ferrari, 514 - Goiabeiras, Vitória - ES | CEP 29075-910