Texto completo
| |
| Autor(es): |
Claudio Nogueira de Meneses
Número total de Autores: 1
|
| Tipo de documento: | Dissertação de Mestrado |
| Imprenta: | Campinas, SP. |
| Instituição: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
| Data de defesa: | 1997-06-20 |
| Membros da banca: |
Cid Carvalho de Souza;
Abilio Pereira de Lucena Filho;
Pedro Jussieu de Rezende;
Carlos Eduardo Ferreira
|
| Orientador: | Cid Carvalho de Souza |
| Resumo | |
Dado um retângulo R e um conjunto finito não vazio P de pontos no interior de R, estudamos o problema de particionar R em retângulos menores tal que nenhum ponto em P está no interior de qualquer retângulo da partição. O objetivo é minimizar a soma dos comprimentos dos segmentos de reta definindo a partição. Este problema é NP-difícil e uma generalização deste tem aplicação em projeto de circuitos VLSI. Neste trabalho implementamos os principais algoritmos de aproximação que têm sido propostos para este problema e propomos dois diferentes modelos de programação linear inteira. No primeiro modelo, onde variáveis são associadas a segmentos de reta, fazemos uma investigação do poliedro associado ao problema. Inequações lineares definindo facets são apresentadas e resultados computacionais para um algoritmo Branch-and-Cut baseado nestas inequações são reportados. O segundo modelo é baseado em uma redução do problema em questão para o problema set partitioning. Um algoritmo Branch-and-Price para este modelo foi implementando e os resultados são comparados com aqueles obtidos pelo algoritmo Branch-and-Cut. Os experimentos computacionais realizados mostraram a viabilidade da resolução exata deste problema através de técnicas de programação linear inteira, pelo menos para instâncias de médio porte (|P| = 200). (AU) | |
| Processo FAPESP: | 96/00945-8 - Resolucao exata do problema de particao retangular de um retangulo com pontos no interior:uma abordagem utilizando combinatoria polie drica. |
| Beneficiário: | Cláudio Nogueira de Meneses |
| Modalidade de apoio: | Bolsas no Brasil - Mestrado |