@techreport{TR-IC-98-35,
  number = {IC-98-35},
  author = {Cláudio Nogueira de Meneses and Cid Carvalho de Souza},
  title = {Exact Solutions of Rectangular Partitions via Integer Programming},
  month = {October},
  year = {1998}, 
  institution = {Institute of Computing, University of Campinas},
  note = {In English, 48 pages.
    \par\selectlanguage{english}\textbf{Abstract}
      We are given a rectangle $R$ in the plane and a finite  set $P$ of $n$
      points in  the interior of  $R$.  A rectangular partition  of $R$ is a
      partition of the surface of $R$ into smaller rectangles. A rectangular
      partition is said to be  feasible with respect to  $P$ if no points in
      $P$ lie in the strict interior of any rectangle of the partition.  The
      length of a  rectangular  partition is  computed  as  the  sum of  the
      lengths of the straight line segments that  define the boundary of its
      rectangles. The  goal  is to  find  a (feasible) rectangular partition
      whose length is minimized. This problem, denoted here by RGP, is
      NP-hard and has  application  in VLSI design.  Several  approximation
      algorithms have been  proposed in the literature to  solve it. In this
      paper we investigate  how to obtain exact  solutions for the  RGP.  We
      introduce  two different  Integer  Programming formulations.   To test
      these formulations  computationally we have implemented a Branch-and-Cut
      algorithm and  a Branch-and-Price  algorithm  for  the first   and the
      second   formulation,  respectively.  Comparisons   between   the  two
      formulations are  made.   The computational  results with  a  randomly
      generated set of  instances show that  it is possible to solve exactly
      medium-sized instances of the RGP.  Moreover, we show that the size of
      the instances  that can be 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.  Finally we also
      have implemented the best approximation algorithm known for RGP
      and we show   that it usually  produces  solutions about 10$\%$  off the
      optimum.
  }
}