A Lagrangean-based decomposition approach for the link constrained Steiner tree problem

摘要

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.