Aarhus University Seal / Aarhus Universitets segl

Using Upper Tolerances in Lagrangian Relaxation for the DCMSTP

Research output: Contribution to conferencePaperResearchpeer-review

  • CORAL - Centre for Operations Research Applications in Logistics
  • Department of Business Studies
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.

Original languageEnglish
Publication year2010
Publication statusPublished - 2010
Event4th Nordic Optimization Symposium - Aarhus, Denmark
Duration: 30 Sep 20102 Oct 2010


Conference4th Nordic Optimization Symposium

See relations at Aarhus University Citationformats

ID: 240474