Aarhus University Seal / Aarhus Universitets segl

Marcel Turkensteen

Upper Tolerances and Lagrangian Relaxation for the DCMSTP

Publikation: KonferencebidragPaperForskningpeer review

Standard

Upper Tolerances and Lagrangian Relaxation for the DCMSTP. / Turkensteen, Marcel.

2011. Paper præsenteret ved European Chapter on Combinatorial Optimization, Amsterdam, Holland.

Publikation: KonferencebidragPaperForskningpeer review

Harvard

Turkensteen, M 2011, 'Upper Tolerances and Lagrangian Relaxation for the DCMSTP', Paper fremlagt ved European Chapter on Combinatorial Optimization, Amsterdam, Holland, 30/05/2011 - 01/06/2011. <http://www.alfaz.nl/eccoxxiv/ECCO24abstracts.pdf>

APA

Turkensteen, M. (2011). Upper Tolerances and Lagrangian Relaxation for the DCMSTP. Paper præsenteret ved European Chapter on Combinatorial Optimization, Amsterdam, Holland. http://www.alfaz.nl/eccoxxiv/ECCO24abstracts.pdf

CBE

Turkensteen M. 2011. Upper Tolerances and Lagrangian Relaxation for the DCMSTP. Paper præsenteret ved European Chapter on Combinatorial Optimization, Amsterdam, Holland.

MLA

Turkensteen, Marcel Upper Tolerances and Lagrangian Relaxation for the DCMSTP. European Chapter on Combinatorial Optimization, 30 maj 2011, Amsterdam, Holland, Paper, 2011.

Vancouver

Turkensteen M. Upper Tolerances and Lagrangian Relaxation for the DCMSTP. 2011. Paper præsenteret ved European Chapter on Combinatorial Optimization, Amsterdam, Holland.

Author

Turkensteen, Marcel. / Upper Tolerances and Lagrangian Relaxation for the DCMSTP. Paper præsenteret ved European Chapter on Combinatorial Optimization, Amsterdam, Holland.

Bibtex

@conference{6d4831f62ad5495fa87ab035bfeade4d,
title = "Upper Tolerances and Lagrangian Relaxation for the DCMSTP",
abstract = "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.",
author = "Marcel Turkensteen",
year = "2011",
language = "English",
note = "null ; Conference date: 30-05-2011 Through 01-06-2011",

}

RIS

TY - CONF

T1 - Upper Tolerances and Lagrangian Relaxation for the DCMSTP

AU - Turkensteen, Marcel

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

M3 - Paper

Y2 - 30 May 2011 through 1 June 2011

ER -