Optimization Online


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

Alexandre Salles da Cunha(acunha***at***dcc.ufmg.br)
Abilio Lucena(abiliolucena***at***globo.com)

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.

Download: [PDF]

Entry Submitted: 04/10/2008
Entry Accepted: 04/11/2008
Entry Last Modified: 04/10/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society