Partição retangular minima de um retangulo em programação linear inteira

Autor(es)

Claudio Nogueira de Meneses

• 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