The problem of packing ellipsoids consists in arranging a given collection of ellipsoids within a particular set. The ellipsoids can be freely rotated and translated, and must not overlap each other. A particular case of this problem arises when the ellipsoids are balls. The problem of packing balls has been the subject of intense theoretical and empirical research. In particular, many works have tackled the problem with optimization tools. On the other hand, the problem of packing ellipsoids has received more attention only in the past few years. This problem appears in a large number of practical applications, such as the design of high-density ceramic materials, the formation and growth of crystals, the structure of liquids, crystals and glasses, the flow and compression of granular materials, the thermodynamics of liquid to crystal transition, and, in biological sciences, in the chromosome organization in human cell nuclei. In this work, we deal with the problem of packing ellipsoids within compact sets from an optimization perspective. We introduce continuous and differentiable nonlinear programming models and algorithms for packing ellipsoids in the n-dimensional space. We present two different models for the non-overlapping of ellipsoids. As these models have quadratic numbers of variables and constraints, we also propose an implicit variables models that has a linear number of variables and constraints. We also present models for the inclusion of ellipsoids within half-spaces and ellipsoids. By applying a simple multi-start strategy combined with a clever choice of starting guesses and a nonlinear programming local solver, we present illustrative numerical experiments that show the capabilities of the proposed models. / O problema de empacotamento de elipsoides consiste em arranjar uma dada coleção de elipsoides dentro de um determinado conjunto. Os elipsoides podem ser rotacionados e transladados e não podem se sobrepor. Um caso particular desse problema surge quando os elipsoides são bolas. O problema de empacotamento de bolas tem sido alvo de intensa pesquisa teórica e experimental. Em particular, muitos trabalhos têm abordado esse problema com ferramentas de otimização. O problema de empacotamento de elipsoides, por outro lado, começou a receber mais atenção apenas recentemente. Esse problema aparece em um grande número de aplicações práticas, como o projeto de materiais cerâmicos de alta densidade, na formação e crescimento de cristais, na estrutura de líquidos, cristais e vidros, no fluxo e compressão de materiais granulares e vidros, na termodinâmica e cinética da transição de líquido para cristal e em ciências biológicas, na organização de cromossomos no núcleo de células humanas. Neste trabalho, tratamos do problema de empacotamento de elipsoides dentro de conjuntos compactos do ponto de vista de otimização. Introduzimos modelos de programação não-linear contínuos e diferenciáveis e algoritmos para o empacotamento de elipsoides no espaço n-dimensional. Apresentamos dois modelos diferentes para a não-sobreposição de elipsoides. Como esses modelos têm números quadráticos de variáveis e restrições em função do número de elipsoides a serem empacotados, também propomos um modelo com variáveis implícitas que possui uma quantidade linear de variáveis e restrições. Também apresentamos modelos para a inclusão de elipsoides em semi-espaços e dentro de elipsoides. Através da aplicação de uma estratégia multi-start simples combinada com uma escolha inteligente de pontos iniciais e um resolvedor para otimização local de programas não-lineares, apresentamos experimentos numéricos que mostram as capacidades dos modelos propostos.
| Identifer | oai:union.ndltd.org:IBICT/oai:teses.usp.br:tde-24022017-134632 |
| Date | 06 November 2015 |
| Creators | Rafael Durbano Lobato |
| Contributors | Ernesto Julian Goldberg Birgin, Reinaldo Morabito Neto, José Mario Martinez Perez, Sandra Augusta Santos, Yoshiko Wakabayashi |
| Publisher | Universidade de São Paulo, Ciência da Computação, USP, BR |
| Source Sets | IBICT Brazilian ETDs |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da USP, instname:Universidade de São Paulo, instacron:USP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0019 seconds