^{1} CORAL - Centre for Operations Research Applications in Logistics, Aarhus School of Business, Aarhus BSS, Aarhus University^{2} Department of Business Studies, Aarhus School of Business, Aarhus BSS, Aarhus University^{3} Department of Economics and Business Economics, Aarhus BSS, Aarhus University^{4} Department of Economics and Business Economics, Aarhus BSS, Aarhus University

Abstract:

We consider the NP-hard degree-constrained Minimum Spanning Tree Problem (DCMSTP). A solution, or spanning tree, is feasible if each vertex is connected to every other one and the number of edges adjacent to each vertex is not larger than a predefined number d. The problem without degree-constraints, the Minimum Spanning Tree Problem (MSTP), is polynomially solvable. We solve the DCMSTP using Lagrangian relaxation. This is the approach in which constraint violations are penalized in the objective function. In an iterative process, the penalty values of violated constraints are increased, and if the constraint is not binding and the penalty value is positive, the penalty value is decreased. A condition for optimality is that the constraints with slack have a penalty value of zero. In Lagrangian relaxation, it generally takes a long time until the penalty values converge. Therefore, the result is often used to approximate the optimal solution value. We present a Lagrangian approach that, as in Volgenant (1989), penalizes violations of the degree-constraints of each vertex. The penalty of a vertex is added to the costs of all edges adjacent to the vertex. Our approach uses upper tolerances of the ordinary MSTP, which are, roughly spoken, the increase in an edge's cost value needed to remove it from the solution. We show that, if the edge costs of at most d edges adjacent to a vertex do not increase by more than their respective upper tolerance values, the optimal tree with updated penalty values will contain at least d edges adjacent to the vertex. Thus, we can determine by how much the penalty values can be increased without creating both slack and a positive penalty for any constraint. Using this finding, our approach is able to obtain accurate penalty values quickly.