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.