查看文章

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 …