Modelos Matemáticos e Estudo Algorítmico para Problemas de Fuga de Retângulos

• Processo: 15/06975-9
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de junho de 2015
• Data de Término da vigência: 30 de novembro de 2015
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Cid Carvalho de Souza
• Beneficiário: Allan Sapucaia Barboza
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Geometria computacional Combinatória poliédrica Programação linear inteira Heurística Benchmarks Otimização combinatória Modelos matemáticos
• Palavra(s)-Chave do Pesquisador: Combinatória Poliédrica | Fuga de Retângulos | Geometria Computacional | Otimização Combinatória | programação linear inteira | Otimização Combinatória

Resumo

Neste trabalho, estudaremos formulações de programação linear inteira e heurísticas para Problemas de Fuga de Retângulos, que surgem no projeto de circuitos integrados. Dados uma placa base retangular e componentes representados por retângulos com eixos paralelos aos da placa, deseja-se conectar os componentes ao barramento situado nas bordas da placa. Essa conexão é feita projetando-se um dos lados do componente em direção às bordas. A densidade em um ponto na placa é definida pelo número de retângulos estendidos que passam sobre esse ponto. São definidos então dois problemas. No primeiro deseja-se conectar todos os componentes minimizando a densidade máxima e no segundo deseja-se conectar o máximo de componentes respeitando uma densidade máxima fixa. Ambos os problemas são NP-difícil. O objetivo da pesquisa é investigar esses problemas através de um estudo poliédrico que leve a um algoritmo exato e do desenvolvimento de heurísticas, analisando estas alternativas experimentalmente sobre um benchmark que deverá ser colocado em domínio público. Além disso, pretendemos desenvolver uma interface gráfica para visualizar instâncias e avaliar as soluções geradas pelos algoritmos implementados.