FERREIRA, Mardson da Silva. Problema do arranjo linear mínimo. 2016. 69 f. Dissertação (Mestrado em Ciência da Computação)-Universidade Federal do Ceará, Fortaleza, 2016. / Submitted by Anderson Silva Pereira (anderson.pereiraaa@gmail.com) on 2017-01-10T20:22:09Z
No. of bitstreams: 1
2016_dis_msferreira.pdf: 1134504 bytes, checksum: 8ad24fa36a9ff4306ff861c7a5b40f12 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2017-01-11T15:39:52Z (GMT) No. of bitstreams: 1
2016_dis_msferreira.pdf: 1134504 bytes, checksum: 8ad24fa36a9ff4306ff861c7a5b40f12 (MD5) / Made available in DSpace on 2017-01-11T15:39:52Z (GMT). No. of bitstreams: 1
2016_dis_msferreira.pdf: 1134504 bytes, checksum: 8ad24fa36a9ff4306ff861c7a5b40f12 (MD5)
Previous issue date: 2016 / Let G = (V, E) be a simple and undirected graph of set of vertices V and set of edges E. Given an assignment of distinct labels in {1, · · · , |V |} to the vertices of G, for every edge uv ∈ E, we define its weight as the absolute difference of labels given to its end nodes. The minimum linear arrangement problem (MinLA) consists in finding a labeling of the vertices of G such that the sum of the weights of its edges is minimized. MinLA is an NP-Hard problem whose corresponding polyhedron has a factorial number of extreme points. In this work, we investigate a recent quadratic model for the MinLA presenting O(|V |² ) variables and O(|V |² ) constraints. This model has the smallest number of variables and constraints among all models in the literature for the problem. We present some theoretical results for the quadratic model, and show how to obtain a mixed linear model whose optimal solution is the same of the quadratic one. We also present valid inequalities for the proposed models. We discuss two heuristics for the problem and propose a column generation algorithm and a specialized Branch and Bound for MinLA. Computational experiments show that the new quadratic and mixed linear models performed better than existing ones in the literature for new and benchmark instances of this problem. / 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 ∈ 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 |² ) variáveis e O(|V |² ) 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 é a mesma 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.
| Identifer | oai:union.ndltd.org:IBICT/oai:www.repositorio.ufc.br:riufc/21501 |
| Date | January 2016 |
| Creators | Ferreira, Mardson da Silva |
| Contributors | Andrade, Rafael Castro de |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Repositório Institucional da UFC, instname:Universidade Federal do Ceará, instacron:UFC |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0017 seconds