In telecommunication networks, full connectivity resilience to multiple link failures is too costly as it requires a network topology with too many redundant links. Alternatively, the connectivity resilience of a telecommunications network can be improved by resorting to available third-party networks for temporary additional connectivity until the failing links are restored. In this approach, some nodes of the network must be selected in advance to act as gateway nodes to the third-party networks when a multiple link failure event occurs. For a given network topology and a cost associated with each node to turn it into a gateway node to each of the third-party networks, the aim is to select the gateway nodes providing maximum connectivity resilience at minimum cost. The Gateway Node Selection is defined as a bi-objective optimization problem such that its Pareto-optimal solutions represent different trade-offs between cost and connectivity resilience. In this work, the connectivity resilience is modeled by the Critical Link Detection optimization problem. An exact optimization algorithm is proposed, based on a row generation algorithm and on set cover cuts. The computational results demonstrate the effectiveness of the proposed algorithm on four well-known telecommunication network topologies.