Seminário de Otimização Combinatória Elder Magalhaes Macambira Sexta-feira, 17 de maio sala: IC2-96 horario: 18hs Resumo: ======= Neste seminário será discutido um problema de otimização combinatória que surge no planejamento de redes de telecomuniçações. O problema consiste em particionar um conjunto de localidades da rede dentro de anéis SONET. Cada anel possui uma mesma capacidade, e cada localidade deve ser atribuída a um único anel. O tráfego de demandas entre as localidades pertencentes a anéis diferentes ficará a cargo de um anel especial denominado anel federal. O objetivo é projetar uma rede backbone com um número mínimo de anéis que atendam às restrições de capacidades estabelecidas para os anéis. Tal problema é denominado problema de atribuição de localidades a anéis SONET (denotado por SRAP). Uma alternativa para resolver o SRAP de forma exata é formulá-lo como um programa linear inteiro (PLI) e usar um resolvedor de Programação Linear para computar o modelo. Assim, serão apresentadas diferentes formulações do SRAP como um PLI. Ocorre que usualmente os modelos lineares para este problema tendem a ser muito difíceis mesmo para os melhores resolvedores de Programação Linear. Isso se deve à baixa qualidade das suas relaxações lineares as quais geram limitantes duais que são incapazes de guiar de modo conveniente os algoritmos de branch-and-bound implementados nestes resolvedores. Uma alternativa seria obter relaxações lineares com limitantes duais melhores. Essa melhoria pode ser obtida, por exemplo, com o emprego de relaxação Lagrangeana ou com o empreago de planos-de-corte. Uma outra técnica, que geralmente induz a obtenção de bons limitantes, consiste em considerar uma formulação alternativa para um problema de otimização combinatória (isto é, uma formulação que contém um número muito grande de variáveis). Tal técnica é denominada geração de colunas. Neste seminário, investigamos o emprego de geração de colunas para prover bons limitantes duais para o SRAP.