Algorithms & Software

Consider a project involving packing ellipsoids of given (but varying) dimensions into a finite container in a way that minimizes the maximum overlap between adjacent ellipsoids. A bilevel optimization algorithm is described for finding local solutions, for both the general case and the easier special case in which the ellipsoids are spheres. Algorithm and analysis tools from semi-definite programming and trust-region methods are key to the approach. The goal is to apply the method to the problem of chromosome arrangement in cell nuclei, and compare our results with the experimental observations reported in the biological literature.