Abílio Lucena

A Hybrid Relax-and-Cut/Branch-and-Cut Algorithm for the Degree-Constrained Minimum Spanning Tree Problem

  • Alexandre Cunha
  • Abílio Lucena
    • Categories Branch and Cut Algorithms, Telecommunications Tags , , ,

    A new exact solution algorithm is proposed for the Degree-Constrained Minimum Spanning Tree Problem. The algorithm involves two combined phases. The first one contains a Lagrangian Relax-and-Cut procedure while the second implements a Branch-and-Cut algorithm. Both phases rely on a standard formulation for the problem, reinforced with Blossom Inequalities. An important feature of the proposed … Read more

    Solving diameter constrained minimum spanning tree problems in dense graphs

  • Abílio Lucena
  • Celso C. Ribeiro
  • Andrea Santos
    • Categories 0-1 Programming, Branch and Cut Algorithms, Telecommunications Tags , , ,

    In this study, a lifting procedure is applied to some existing formulations of the Diameter Constrained Minimum Spanning Tree Problem. This problem typically models network design applications where all vertices must communicate with each other at minimum cost, while meeting or surpassing a given quality requirement. An alternative formulation is also proposed for instances of … Read more

    STRONG LOWER BOUNDS FOR THE PRIZE COLLECTING STEINER PROBLEM IN GRAPHS

  • Abílio Lucena
  • Mauricio G.C. Resende
    • Categories Combinatorial Optimization, Network Optimization, Telecommunications Tags , , ,

    Given an undirected graph G with nonnegative edges costs and nonnegative vertex penalties, the prize collecting Steiner problem in graphs (PCSPG) seeks a tree of G with minimum weight. The weight of a tree is the sum of its edge costs plus the sum of the penalties of those vertices not spanned by the tree. … Read more