The Generalized Steiner Problem with Edge-Connectivity constraints (GSP-EC) consists of computing the minimal cost subnet- work of a given feasible network where some pairs of nodes must satisfy edge-connectivity requirements. It can be applied in the design of com- munications networks where connection lines can fail and is known to be an NP-Complete problem. In this paper we introduce an algorithm based on GRASP (Greedy Randomized Adaptive Search Procedure), a combinatorial optimization metaheuristic that has proven to be very ef- fective for such problems. Promising results are obtained when testing the algorithm over a set of heterogeneous network topologies and con- nectivity requirements; in all cases with known optimal cost, optimal or near-optimal solutions are found.
['Pablo Sartor', 'Franco Robledo']
Solving the Generalized Steiner Problem in Edge-Survivable Networks