Problemas de classificação com restrições de conexidade flexibilizadas
AUTOR(ES)
Eduardo Uchoa Barboza
DATA DE PUBLICAÇÃO
1997
RESUMO
A classificação de dados consiste em separar um conjunto de objetos, descritos por um conjunto de dados, em classes, de forma a que objetos na mesma classe sejam semelhantes entre si. A classificação freqüentemente é usada como uma ferramenta de pesquisa científica. Os objetivos de uma classificação podem diferir de acordo com as necessidades e com a origem dos dados sobre os objetos a classificar. Em alguns contextos existe interesse em associar os objetos aos vértices de um grafo, de forma que a semelhança entre os objetos esteja relacionada a proximidade nesse grafo. Os métodos existentes, para aplicações nestes contextos~ obrigam cada classe a formar um único componente conexo dentro do grafo. Chamamos essa abordagem de conexidade estrita e propomos a idéia de classificação com conexidade flexibilizada, ou seja a concepção de métodos que permitam a um usuário especificar o número de componentes de cada classe no grafo e mostramos porque essa flexibilização é desejável. Em seguida, estudamos a resolução de um problema computacional resultante da flexibilização da conexidade, o Problema da Atribuição ?-Conexa (PAgC). Demonstramos a NP-completude desse problema e apontamos alguns casos polinomiais. Então, concentramo-nos no estudo de diferentes formas para modelar matematicamente a conexidade flexibilizada. Os resultados obtidos podem ser naturalmente aplicados a outros problemas onde tal conexidade é necessária. Finalmente, propomos dois algoritmos para resolver (PAgC). Um baseado na técnica de branch-and-bound e outro na de branch-and-price. Uma comparação dos resultados obtidos por cada técnica é apresentada na seqüência. em estudo de classes de desigualdades válidas, capazes de melhorar substancialmente ambos os algoritmos, conclui a dissertação
ASSUNTO(S)
programação inteira pesquisa operacional otimização combinatoria
ACESSO AO ARTIGO
http://libdigi.unicamp.br/document/?code=000118277Documentos Relacionados
- Busca de soluções otimas em problemas de roteamento com restrições temporais
- Solução de problemas de planejamento florestal com restrições de inteireza utilizando busca tabu
- Metaheurística algoritmo genético para solução de problemas de planejamento florestal com restrições de integridade
- Metaheurística Simulated Annealing para solução de problemas de planejamento florestal com restrições de integridade
- Modelos matemáticos para problemas de dimensionamento de lotes com restrições de capacidade e custos de transporte