Optimal placement of rectangles on a plane with fixed objects

Abstract

Consider a region on a plane with a set of points with positive weights and rectangles that have to be place in that region without intersections. Either the maximal sum of weights of the points in rectangles or the total sum must be minimal. We consider the case of two rectangles. The original continuous problem is reduced to a discrete one by introducing equivalence classes. We propose polynomial combinatorial algorithms for solving the problem. We conduct a computational experiment to compare the efficiency of developed algorithms with the IBM ILOG CPLEX suite with an integer programming model.