@techreport{TR-IC-01-16,
number = {IC-01-16},
author = {Felipe C. Calheiros and AbĂlio Lucena and Cid C. {de Souza}},
title = {Optimal Rectangular Partitions},
month = {December},
year = {2001},
institution = {Institute of Computing, University of Campinas},
note = {In English, 29 pages.
\par\selectlanguage{english}\textbf{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 defined it. The partition is said to be feasible if no
point of $P$ is interior to a partition rectangle. The
Rectangular Partitioning Problem (RGP) seeks a feasible
rectangular partition of $R$ with the least length.
Computational evidence from the literature indicates that RGPs
with non corectilinear points in $P$, denoted RGNLPs, are the
hardest to solve to proven optimality. In this paper, some
structural properties of optimal feasible RGNLP partitions are
presented. These properties allow for 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 RGNLP instances more
than twice as large as those found in the literature.
\par
{\bf Keywords:} Rectangular partitions, optimality properties,
Lagrangian relaxation, cutting planes.
}
}