Linear Tarification in Multi-Commodity Telecommunications Networks

We consider the problem of determining a set ofoptimal tariffs for a revenue maximizing operator, on a subset ofall arcs of a telecommunications network. We suppose multiplerational clients are active on the network who route their demandson the cheapest paths from source to destination, where the costof a path is determined by all costs and tariffs on the arcs ofthe path.The complexity of the problem is studied first. Second, we proposea remodeling of the network, combined with model specific graphreduction methods. This new model is used in a branch and boundalgorithm to solve the problem to optimality. Finally, we providecomputational results which show the efficiency of our method fora number of real-life instances.