Network cost minimization using threshold-based discounting

A network design problem in which every pair of nodes can communicate directly is discussed. However, there is an incentive to combine flow from different sources, namely, if the total flow through a link exceeds the prescribed threshold, then the cost of this flow is discounted by a factor α. Alternative mixed integer linear formulations for this problem are presented. Computational results comparing the models on a set of benchmark problems are also presented. The results show the effectiveness of the formulations: for discounts of 5-10%, the gaps between linear and integer solutions are within few percent. Such a model offers economic incentives in building and utilizing communication networks.