A Hybrid Relax-and-Cut/Branch-and-Cut Algorithm for the Degree-Constrained Minimum Spanning Tree Problem
Alexandre Salles da Cunha(acunhadcc.ufmg.br)
Abstract: 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 algorithm is that, whenever optimality is not proven by Relax-and-Cut alone, an attractive set of valid inequalities is identified and carried over, in a warm start, from Lagrangian Relaxation to Branch-and-Cut. In doing so, without the need of running any separation algorithm, one aims at obtaining an initial Linear Programming relaxation bound at least as good as the best Lagrangian bound previously obtained. Computational results indicate that our hybrid algorithm dominates similar hybrid algorithms based on the standard formulation alone. Likewise, it also dominates pure Branch-and-Cut algorithms based on either the standard formulation or its Blossom Inequalities reinforced version.
Keywords: Branch-and-Cut, Relax-and-Cut, Lagrangian warm start to cutting plane algorithms, Degree-Constrained Minimum Spanning Tree
Category 1: Combinatorial Optimization (Branch and Cut Algorithms )
Category 2: Applications -- OR and Management Sciences (Telecommunications )
Citation: Technical Report, Departamento de Administração, Universidade Federal do Rio de Janeiro, March 2008.
Entry Submitted: 04/10/2008
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|