The multi-weighted Steiner tree problem: A reformulation by intersection

We propose a new formulation for the multi-weighted Steiner tree (MWST) problem. This formulation is based on the fact that a previously proposed formulation for the problem is non-symmetric in the sense that the corresponding linear programming relaxation bounds depend on the node selected as a root of the tree. The new formulation (the reformulation by intersection) is obtained by intersecting the feasible sets of the models corresponding to each possible root selection for the underlying directed problem. Theoretical results will show that the linear programming relaxation of the new formulation dominates the linear programming relaxation of each of the rooted formulations and is comparable with the linear programming bounds of the best formulation known for the problem. A Lagrangean relaxation scheme derived from the new formulation is also proposed and tested, with quite favourable results, on instances with up to 500 nodes and 5000 edges.