@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.
  }
}