Exact approaches for solving robust prize-collecting Steiner tree problems

•The paper deals with the Robust PCStT, addressing interval uncertainty on its data.•Different mathematical programming formulations are proposed.•Branch-and-cut Algorithms are designed and extensively tested.•Recent theoretical results are adapted for the Robust PCStT and some of it variants.

In the Prize-Collecting Steiner Tree Problem (PCStT) we are given a set of customers with potential revenues and a set of possible links connecting these customers with fixed installation costs. The goal is to decide which customers to connect into a tree structure so that the sum of the link costs plus the revenues of the customers that are left out is minimized. The problem, as well as some of its variants, is used to model a wide range of applications in telecommunications, gas distribution networks, protein–protein interaction networks, or image segmentation.In many applications it is unrealistic to assume that the revenues or the installation costs are known in advance. In this paper we consider the well-known Bertsimas and Sim (B&S) robust optimization approach, in which the input parameters are subject to interval uncertainty, and the level of robustness is controlled by introducing a control parameter, which represents the perception of the decision maker regarding the number of uncertain elements that will present an adverse behavior.We propose branch-and-cut approaches to solve the robust counterparts of the PCStT and the Budget Constraint variant and provide an extensive computational study on a set of benchmark instances that are adapted from the deterministic PCStT inputs. We show how the Price of Robustness influences the cost of the solutions and the algorithmic performance.Finally, we adapt our recent theoretical results regarding algorithms for a general class of B&S robust optimization problems for the robust PCStT and its budget and quota constrained variants.