Solving the steiner tree problem with revenues, budget and hop constraints to optimality

Abstract

We investigate the Steiner tree problem with revenues, budget and hop constraints (STPRBH) on graph, which is a generalization of the well-known Steiner tree problem. Given a root node, edge costs, nodes revenues, as well as a preset budget and hop, the STPRBH seeks to find a subtree that includes the root node and maximizes the sum of the total edge revenues respecting the budget and hop constraints. These constraints impose limits on the total cost of the network and the number of edges between any vertex and the root. Not surprisingly, the STPRBH is NP-hard. For this challenging network design problem that arises in telecommunication settings and multicast routing, we present several polynomial size formulations. We propose an enhanced formulation based on the classical work of Miller, Tucker, and Zemlin by using additional set of variables representing the rank-order of visiting the nodes. Also, we investigate a new formulation for the STPRBH by tailoring a partial rank-1 of the Reformulation-Linearization Technique. Extensive results are exhibited using a set of benchmark instances to compare the proposed formulations by using a general purpose MIP solver.