  The optimization version of the cavity method for single instances, called
Max-Sum, has been applied in the past to the Minimum Steiner Tree Problem on
Graphs and variants. Max-Sum has been shown experimentally to give
asymptotically optimal results on certain types of weighted random graphs, and
to give good solutions in short computation times for some types of real
networks. However, the hypotheses behind the formulation and the cavity method
itself limit substantially the class of instances on which the approach gives
good results (or even converges). Moreover, in the standard model formulation,
the diameter of the tree solution is limited by a predefined bound, that
affects both computation time and convergence properties. In this work we
describe two main enhancements to the Max-Sum equations to be able to cope with
optimization of real-world instances. First, we develop an alternative 'flat'
model formulation, that allows to reduce substantially the relevant
configuration space, making the approach feasible on instances with large
solution diameter, in particular when the number of terminal nodes is small.
Second, we propose an integration between Max-Sum and three greedy heuristics.
This integration allows to transform Max-Sum into a highly competitive
self-contained algorithm, in which a feasible solution is given at each step of
the iterative procedure. Part of this development participated on the 2014
DIMACS challenge on Steiner Problems, and we report the results here.
