Mourad Baïou, Francisco Barahona
Networks
This paper presents an algorithm to obtain near optimal solutions for the Steiner tree problem in graphs. It is based on a Lagrangian relaxation of a multi-commodity flow formulation of the problem. An extension of the subgradient algorithm, the volume algorithm, has been used to obtain lower bounds and to estimate primal solutions. It was possible to solve several difficult instances from the literature to proven optimality without branching. Computational results are reported for problems drawn from the SteinLib library.
Mourad Baïou, Francisco Barahona
Networks
Michael E. Henderson
International Journal of Bifurcation and Chaos in Applied Sciences and Engineering
Martin Charles Golumbic, Renu C. Laskar
Discrete Applied Mathematics
Minghong Fang, Zifan Zhang, et al.
CCS 2024