Paper detail

Practical optimization of Steiner Trees via the cavity method

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.