3
$\begingroup$

In the paper (p. 3) and the slides presents the formulation of the Steiner problem on graphs via so called Steiner cuts. But according to the definition, the number of Steiner cuts and so the number of constraints grows exponentially with the number of vertices in the graph.

First question: How to solve the problem in this cut-formulation? After all, we have too many constraints? For example, to solve the problem in the formulation through the multi-commodity flow described in the first article, we have only 'number of terminals' * 'number of vertices' constraints, and this can be solved.

Second question: Is there any practical benefit to solve the LP-relaxed problem, and then improve it with metaheuristics? Or is it the same to build a first Steiner tree aproximation with a greedy algorithm and then improve it?

$\endgroup$
3
$\begingroup$

The LP-relaxation can be solved efficiently (in polynomial time) by using cutting planes, see, e.g., "Solving Steiner tree problems in graphs to optimality" by Koch and Martin for the separation algorithm. This approach is also highly relevant in practice. Often, the LP-relaxation provides already an optimal solution, and if not, branch-and-bound can be used. This approach is used in the currently most successful solver for Steiner tree problems, see https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/8003

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.