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

AUTOR(ES)
DATA DE PUBLICAÇÃO

1997

RESUMO

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

ASSUNTO(S)

otimização matematica programação inteira otimização combinatoria algoritmos

ACESSO AO ARTIGO

Documentos Relacionados