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

Orientador: Cid Carvalho de SouzaDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de ComputaçãoResumo: 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).Abstract: Given a rectangle R in the plane and a non empty finite set P of points in the interior of R, we study the problem of partitioning R into smaller rectangles such that no point in P is interior to any rectangle of the partition. The goal is to minimize the sum of the lengths of the straight line segments defining the partition. This problem is NP-hard and a generalization of it have application in VLSI design. In this work we implement the main approximation algorithms that have been proposed for this problem and propose two different integer programming models. In the first one, the variables are associated to line segments and we investigate the polyhedron associated to this model. Facet defining inequalities are presented and computational results obtained by a Branch-and-Cut algorithm based on these inequalities are reported. The second model is based on a Set Partitioning formulation. A Branch-and-Price algorithm for this model has been implemented and the results are compared with those obtained by the Branch-and-Cut algorithm. The computational results show that, at least for medium sized instances (IPI = 200), the problem can be solved exactly using Integer Programming techniques.MestradoMestre em Ciência da Computaçã