Título: Problema do Arranjo Linear Mínimo

Data: 23/06/2016 Horário: 13:30h Local: Sala de Seminários do Bloco 952

Resumo:

Seja G=(V,E) um grafo simples e não orientado de conjunto de vértices V e conjunto de arestas E. Dada uma atribuição de rótulos distintos em {1,..., |V|} aos vértices de G, para cada aresta uv em E, definimos seu peso como sendo a diferença absoluta entre os rótulos atribuídos às suas extremidades. O problema do arranjo linear mínimo (MinLA) é encontrar uma rotulação dos vértices de G de modo que a soma dos pesos de suas arestas seja mínima. MinLA é um problema NP-Difícil cujo poliedro correspondente tem um número fatorial de pontos extremos. Neste trabalho, investigamos um recente modelo quadrático para o MinLA com O(|V|^2) variáveis e O(|V|^2) restrições. Esse modelo apresenta o menor número de variáveis e restrições dentre todos os modelos da literatura para o problema. Apresentamos alguns resultados teóricos para o modelo quadrático, bem como mostramos como obter um modelo linear misto cuja solução ótima é usada para determinar a solução ótima do modelo quadrático. Propomos igualmente desigualdades válidas para os modelos propostos. Apresentamos duas heurísticas para o problema. Implementamos um algoritmo de geração de colunas e um Branch and Bound especializado. Experimentos computacionais mostram que o novo modelo teve desempenho superior aos demais modelos conhecidos.

Banca:

• Prof. Dr. Rafael Castro de Andrade (MDCC/UFC - Orientador)
• Prof. Dr. Manoel Bezerra Campelo Neto(MDCC/UFC)
• Prof. Dr. Tibérius de Oliveira e Bonates (DEMA/UFC)
• Prof. Dr. Plácido Rogério Pinheiro (UNIFOR)