DSpace Communidade:
http://repositorio.ufla.br/jspui/handle/1/32
2017-11-20T09:21:05ZLower bounds and exact algorithms for the quadratic minimum spanning tree problem
http://repositorio.ufla.br/jspui/handle/1/15628
Título: Lower bounds and exact algorithms for the quadratic minimum spanning tree problem
Autor: Pereira, Dilson Lucas; Gendreau, Michel; Cunha, Alexandre Salles da
Resumo: We address the quadratic minimum spanning tree problem (QMSTP), the problem of finding a spanning tree of a connected and undirected graph such that a quadratic cost function is minimized. We first propose an integer programming formulation based on the reformulation–linearization technique (RLT). We then use the idea of partitioning spanning trees into forests of a given fixed size and obtain a QMSTP reformulation that generalizes the RLT model. The reformulation is such that the larger the size of the forests, the stronger lower bounds provided. Thus, a hierarchy of formulations is obtained. At the lowest hierarchy level, one has precisely the RLT formulation, which is already stronger than previous formulations in the literature. The highest hierarchy level provides the convex hull of integer feasible solutions for the problem. The formulations introduced here are not compact, so the direct evaluation of their linear programming relaxation bounds is not practical. To overcome that, we introduce two lower bounding procedures based on Lagrangian relaxation. These procedures are embedded into two parallel branch-and-bound algorithms. As a result of our study, several instances in the literature were solved to optimality for the first time.2015-11-01T00:00:00ZBranch-and-cut and branch-and-cut-and-price algorithms for the adjacent only quadratic minimum spanning tree problem
http://repositorio.ufla.br/jspui/handle/1/15627
Título: Branch-and-cut and branch-and-cut-and-price algorithms for the adjacent only quadratic minimum spanning tree problem
Autor: Pereira, Dilson Lucas; Gendreau, Michel; Cunha, Alexandre Salles da
Resumo: The quadratic minimum spanning tree problem (QMSTP) consists of finding a spanning tree of a graph G such that a quadratic cost function is minimized. In its adjacent only version (AQMSTP), interaction costs only apply for edges that share an endpoint. Motivated by the weak lower bounds provided by formulations in the literature, we present a new linear integer programming formulation for AQMSTP. In addition to decision variables assigned to the edges, it also makes use of variables assigned to the stars of G. In doing so, the model is naturally linear (integer), without the need of implementing usual linearization steps, and its linear programming relaxation better estimates the interaction costs between edges. We also study a reformulation derived from the new model, obtained by projecting out the decision variables associated with the stars. Two exact solution approaches are presented: a branch-and-cut-and-price algorithm, based on the first formulation, and a branch-and-cut algorithm, based on its projection. Our computational results indicate that the lower bounds introduced here are much stronger than previous bounds in the literature. Being designed for the adjacent only case, our duality gaps are one order of magnitude smaller than the Gilmore–Lawler lower bounds for AQMSTP. As a result, the two exact algorithms introduced here outperform the previous exact solution approaches in the literature. In particular, the branch-and-cut method we propose managed to solve AQMSTP instances with as many as 50 vertices to proven optimality.2015-01-01T00:00:00ZA comparison of several models for the hamiltonian p-median problem
http://repositorio.ufla.br/jspui/handle/1/15610
Título: A comparison of several models for the hamiltonian p-median problem
Autor: Gollowitzer, Stefan; Gouveia, Luis; Laporte, Gilbert; Pereira, Dilson Lucas; Wojciechowski, Adam
Resumo: The Hamiltonian p-median problem consists of determining p disjoint cycles of minimum total cost covering all vertices of a graph. We present several new and existing models for this problem, provide a hierarchy with respect to the quality of the lower bounds yielded by their linear programming relaxations, and compare their computational performance on a set of benchmark instances. We conclude that three of the models are superior from a computational point of view, two of which are introduced in this article2014-07-01T00:00:00ZApplying information retrieval techniques to detect duplicates and to rank references in the preliminary phases of systematic literature reviews
http://repositorio.ufla.br/jspui/handle/1/15596
Título: Applying information retrieval techniques to detect duplicates and to rank references in the preliminary phases of systematic literature reviews
Autor: Morais, Ramon Abilio Flávio; Vale, Gustavo; Oliveira, Claudiane; Pereira, Denilson Alves; Costa, Heitor
Resumo: Systematic Literature Review (SLR) is a means to synthesize relevant and high quality studies
related to a specific topic or research questions. In the Primary Selection stage of an SLR, the
selection of studies is usually performed manually by reading title, abstract, and keywords of
each study. In the last years, the number of published scientific studies has grown increasing the
effort to perform this sort of reviews. In this paper, we proposed strategies to detect non-papers
and duplicated references in results exported by search engines, and strategies to rank the
references in decreasing order of importance for an SLR, regarding the terms in the search string.
These strategies are based on Information Retrieval techniques. We implemented the strategies
and carried out an experimental evaluation of their applicability using two real datasets. As
results, the strategy to detect non-papers presented 100% of precision and 50% of recall; the
strategy to detect duplicates detected more duplicates than the manual inspection; and one of the
strategies to rank relevant references presented 50% of precision and 80% of recall. Therefore,
the results show that the proposed strategies can minimize the effort in the Primary Selection
stage of an SLR.2015-08-01T00:00:00Z