A new quadratic relaxation for binary variables with applications to the reliability of electrical distribution networks, segmentation of nerve root images, and distance geometry problems
Petra Maria Bartmeyer
Abstract
Resumo: Como o título sugere, o foco desta pesquisa é o desenvolvimento de uma nova relaxação quadrática para problemas binários, sua formalização em resultados teóricos, e a aplicação dos novos conceitos em aplicações à confiabilidade de redes de energia elétrica, à segmentação de imagens médicas de nervos e à problemas de geometria de distâncias. Modelos matemáticos contendo va-riáveis de decisões binárias podem ser usados para encontrar as melhores soluções em processos de tomada de decisões, normalmente caracterizando problemas de otimização combinatória difíceis. A solução desses problemas em aplicações de interesse prático requer um grande esforço computacional; por isso, ao longo dos últimos anos, têm sido objeto de pesquisas na área de metaheurísticas. As ideias aqui desenvolvidas abrem novas perspectivas para a abordagem desses problemas apoiando-se em métodos de otimização não-lineares, área que vem sendo povoada por "solvers" muito eficientes. Inicialmente, explorando aspectos formais, a relaxação desenvolvida é parti-cularizada para um problema de otimização quadrática binária irrestrita. O relaxamento permite o desenvolvimento de três estruturas para abordar esta classe de problemas, e explora a convexidade da função objetivo para obter melhorias computacionais. Estudos de casos compararam o relaxamento proposto com os relaxamentos similares apresentados na literatura. Foram desenvolvidas três aplicações para os desenvolvimentos teóricos da pesquisa. A primeira aplicação envolve a melhoria da confiabilidade de redes de energia elétrica. Especificamente, aborda o problema de definir a melhor alternativa para a alocação de sensores na rede, o que permite reduzir os efeitos de ocorrências indesejáveis e ampliar a resiliência das redes. A segunda aplicação envolve o problema de segmentação de imagens médicas associadas a estruturas de nervos. A abordagem proposta interpreta o problema de segmentação como um problema de otimização binária, onde medir cada axônio significa encontrar um ciclo Hamiltoniano, um caso do problema do caixeiro viajante; a solução desses problemas fornece a estatística descritiva para um conjunto de axônios, incluindo o número (de axônios), os diâmetros e as áreas ocupadas. A última aplicação elabora um modelo matemático para o problema de geometria de distâncias sem designação, área ainda pouco estudada e com muitos aspectos em aberto. A relaxação desenvolvida na pesquisa permitiu resolver instâncias com mais de vinte mil variáveis binárias. Esses resultados são bons indicadores dos benefícios alcançáveis com os aspectos teóricos da pesquisa, e abrem novas perspectivas para as aplicações, que incluem inovações em nanotecnologia e bioengenharia