Please use this identifier to cite or link to this item: http://www.repositorio.ufc.br/handle/riufc/21501
Title in Portuguese: Problema do arranjo linear mínimo
Title: Minimum linear arrangement problem
Author: Ferreira, Mardson da Silva
Advisor(s): Andrade, Rafael Castro de
Keywords: Otimização combinatória
Programação matemática
Arranjo linear mínimo
Issue Date: 2016
Citation: FERREIRA, M. S. (2016)
Abstract in Portuguese: 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.
Abstract: 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.
Description: 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.
URI: http://www.repositorio.ufc.br/handle/riufc/21501
Appears in Collections:DCOMP - Dissertações defendidas na UFC

Files in This Item:
File Description SizeFormat 
2016_dis_msferreira.pdf1,11 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.