Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/66229
Type: Artigo de periódico
Title: Exact solutions of rectangular partitions via integer programming
Author: De Meneses, CN
De Souza, CC
Abstract: Given a rectangle R in the plane and a finite set P of points in its interior, consider the partitions of the surface of R into smeller rectangles. A partition is feasible with respect to P if each point in P lie on the boundary of some rectangle of the partition. The length of a partition is computed as the sum of the lengths of the line segments defining the boundary of its rectangles. The goal is to find a feasible partition with minimum length. This problem, denoted by RGP, belongs to NP-hard and has application in VLSI design. In this paper we investigate how to obtain exact solutions for the RGP. We introduce two different Integer Programming formulations and carry out a theoretical study to evaluate and compare the strength of their bounds. Computational experiments are reported for Branch-and-Cut and Branch-and-Price algorithms we have implemented for the first and the second formulation, respectively. Randomly generated instances with \P\ less than or equal to 200 are solved exactly. The tests indicate that the size of the instances solved with our algorithms decrease by an order of magnitude in the absence of corectilinear points in P, a special case of RGP whose complexity is still open.
Subject: rectangular partition
polyhedral combinatorics
branch-and-cut
branch-and-price
Country: Singapura
Editor: World Scientific Publ Co Pte Ltd
Rights: fechado
Identifier DOI: 10.1142/S0218195900000280
Date Issue: 2000
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
WOS000165581100003.pdf5.4 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.