A Lagrangean-based decomposition approach for the link constrained Steiner tree problem. (4th May 2018)

• Record Type: Journal Article
• Authors: Di Puglia Pugliese, Luigi; Gaudioso, Manlio; Guerriero, Francesca; Miglionico, Giovanna
• Is Part Of: Optimization methods and software. Volume 33:Number 3(2018)
• Page Start: 650
• Page End: 670
• Publication Date: 2018-05-04
• Subjects: constrained Steiner tree -- decomposition approach -- Lagrangean relaxation; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2017.1392518
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : The link constrained Steiner tree problem is a variant of the classic Steiner tree problem where the number of links to be activated must not exceed a pre-fixed value. We introduce a multi-start heuristic to obtain a quick feasible solution. The proposed heuristic is embedded into a decomposition framework based on Lagrangean relaxation. In particular, the relaxed problem is decomposed into two polynomially solvable subproblems and, to tackle the Lagrangean dual, we introduce a dual ascent procedure where just one multiplier at a time is updated. Our approach can be classified as a Lagrangean heuristic. In fact, at each iteration of the dual ascent procedure, the information derived from the solution of the relaxed problem is used to provide a feasible solution, by solving a restricted problem defined on an appropriate subgraph. Several versions of the proposed approach are defined and tested on instances drawn from the scientific literature.