Otimização de layouts como um problema de Steiner: uma abordagem via programação não linear

Abstract

Este trabalho propõe uma abordagem para a otimização de layouts de circuitos eletrônicos, abordando o problema como uma variante do Problema da Árvore de Steiner. Ao representar circuitos como grafos, onde os terminais correspondem aos pontos de conexão e os pontos adicionais (pontos de Steiner) são introduzidos para reduzir o comprimento total das interconexões, a metodologia integra técnicas de programação não linear para atender às restrições reais de circuitos complexos. O trabalho abrange a fundamentação teórica dos métodos de otimização, a modelagem matemática e a implementação de um algoritmo que, aliado à análise estatística dos resultados, demonstra a rapidez da abordagem na redução de comprimentos de fios. Os experimentos indicam que a utilização de pontos de Steiner, em conjunto com a programação não linear, possibilita soluções adaptáveis às matrizes de incidência dos grafos em circuitos planares.