Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/81625
Type: Artigo de periódico
Title: Optimal rectangular partitions
Author: Calheiros, FC
Lucena, A
de Souza, CC
Abstract: Assume that a rectangle R is given on the Euclidean plane together with a finite set P of points that are interior to R. A rectangular partition of R is a partition of the surface of R into smaller rectangles. The length of such a partition equals the sum of the lengths for the line segments that define it. The partition is said to be feasible if no point of P is interior to a partition rectangle. The Rectangular Partitioning Problem (RPP) seeks a feasible rectangular partition of R with the least length. Computational evidence from the literature indicates that RPPs with noncorectilinear points in P, denoted NCRPPs, are the hardest to solve to proven optimality. In this paper, some structural properties of optimal feasible NCRPP partitions are presented. These properties allow substantial reductions in problem input size to be carried out. Additionally, a stronger formulation of the problem is also made possible. Based on these ingredients, a hybrid Lagrangian Relaxation-Linear Programming Relaxation exact solution algorithm is proposed. Such an algorithm has proved capable of solving NCRPP instances more than twice as large as those found in the literature. (C) 2002 Wiley Periodicals, Inc.
Subject: rectangular partitions
optimality properties
Lagrangian relaxation
cutting planes
Country: EUA
Editor: John Wiley & Sons Inc
Rights: fechado
Identifier DOI: 10.1002/net.10058
Date Issue: 2003
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
WOS000180208300006.pdf172.41 kBAdobe PDFView/Open


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