Aarhus University Seal

Upper Tolerances and Lagrangian Relaxation for the DCMSTP

Research output: Contribution to conferencePaperResearchpeer-review

The Degree-Constrained Minimum Spanning Tree Problem (DCMSTP) is the problem of connecting a set of vertices against minimum cost, where no more than a prespecified number of edges may enter or leave each vertex. The DCMSTP is an NP-hard problem with many practical applications in the design of networks. Many efficient solution methods for the DCMSTP rely on Lagrangian relaxation for the tight lower bounds needed to solve instances.

Lagrangian procedures for the DCMSTP solve a modified version of the regular Minimum Spanning Tree Problem (MSTP) in which the degree constraint violations are penalized in the objective function. By varying the penalty values, or multipliers, the procedures can increase the resulting lower bound value. Existing Lagrangian procedures start with multiplier values equal to 0 and then iteratively adjust them. The upper tolerance based (UTB) approach from this paper supplements Lagrangian relaxation approaches by using the upper tolerances of the MSTP, which correspond to the increase in an edge weight needed to remove the edge from an MSTP solution, to set the accurate initial multiplier values. The UTB approach enables Lagrangian relaxation approaches to find better bounds within their given running times.
Original languageEnglish
Publication year2011
Publication statusPublished - 2011
EventEuropean Chapter on Combinatorial Optimization - Amsterdam, Netherlands
Duration: 30 May 20111 Jun 2011


ConferenceEuropean Chapter on Combinatorial Optimization

See relations at Aarhus University Citationformats

ID: 35438618