Partições retangulares otimas : algoritmos lagrangeanos e planos de corte

Seja P um conjunto finito de pontos do plano localizados no interior de um retângulo R. Considere as partições de R em retângulos menores. Se nenhum ponto de P for interior a algum destes retângulos, então a partição é viável e seu custo é a soma do comprimento dos segmentos que a definem. O problema de partição retangular (RG-P) busca uma partição retangular de R de custo mínimo. Experimentos descritos na literatura envolvendo algoritmos exatos para esse problema indicam que instâncias do RG-P com pontos não corretilineares em P, chamado de RG-NLP, são as mais difíceis de serem resolvidas até a otimalidade. Esse trabalho apresenta propriedades geométricas de soluções ótimas do RGNLP, que permitem uma redução substancial do número de variáveis do modelo natural de programação inteira. Adicionalmente, essas propriedades levam a desigualdades satifeitas por todas as soluçoes ótimas. Tais desigualdades são usadas em um algoritmo de Relaxação Lagrangeana com Planos de Corte (Relax and Cut). Enquanto resolvedores de programação linear não conseguem computar o enorme modelo para instâncias do RG-NLP, o algoritmo lagrangeano produziu excelentes limitantes. Além disso, para as instâncias em que este algoritmo não foi capaz de provar otimalidade, o número de variáveis eliminadas durante a sua execução foi suficiente para permitir a execução do resolvedor de programação linear. O algoritmo híbrido combinando a Relaxação Lagrangeana e Programação Linear foi capaz de resolver instâncias mais do que duas vezes maiores que as apresentadas na literatura. Além disso, os grandes modelos de partição gerados e resolvidos neste trabalho figuram entre os maiores já resolvidos até a otimalidadeLet P be a finite set of points in the plane lying in the interior of a rectangle R. Consider the partitions of R into smaller rectangles. Ir no point in P is interior to any such rectangle, the partition is feasible and its length is the sum of the lengths of the segments defining it. The Rectangular Partition Problem (RG-P) seeks for a feasible partition of R of minimum length. Experiments reported in the literature with exact algorithms based on Integer Programming (IP) indicate that RG-P instances with non corectilinear points in P, called RG-NLP, are the hardest to solve to optimality. This work presents structural properties of optimal RG-NLP solutions which allow for substantial reductions on the number of variables in the natural IP model of the problem. In addition, these properties led to inequalities that are satisfied by alI optimal solutions. Such inequalities are used in a Lagrangean Relax and Cut algorithm for RG-NLP. While commercial LP solvers cannot compute the huge models for RG-NLP instances in general, the Lagrangean algorithm produces very good bounds. For the few test instances where Lagrangean bounds alone are not enough to prove optimality, they allow enough variables to be fixed that an LP solver can now be applied. The hybrid algorithm combining the Lagrangean and the LP phases solves RG-NLP instances more than twice as large as those in the literature. Additionally, the large set partitioning instances solved with this algorithm figure among the biggest ever solved to prove optimalit