An algorithm to find the link constrained steiner tree in undirected graphs

We address a variant of the classical Steiner tree problem defined over undirected graphs. The objective is to determine the Steiner tree rooted at a source node with minimum cost and such that the number of edges is less than or equal to a given threshold. The link constrained Steiner tree problem (LCST P) belongs to the NP-hard class. We formulate a Lagrangian relaxation for the LCST P in order to determine valid bounds on the optimal solution. To solve the Lagrangian dual, we develop a dual ascent heuristic based on updating one multiplier at time. The proposed heuristic relies on the execution of some sub-gradient iterations whenever the multiplier update procedure is unable to generate a significant increase of the Lagrangian dual objective. We calculate an upper bound on the LCST P by adjusting the infeasibility of the solution obtained at each iteration. The solution strategy is tested on instances inspired by the scientific literature.