Maximum throughput network routing subject to fair flow allocation

We investigate a bilevel network routing problem where, given a directed graph with a capacity for each arc and a set of elastic traffic demands specified by the corresponding origin-destination pairs, the network operator has to select a single path for each pair so as to maximize the total throughput while assuming that the flows are allocated over the chosen paths according to a fairness principle. We consider max-min fair flow allocation as well as maximum bottleneck flow allocation. After presenting a complexity result, we discuss MILP formulations for the two problem versions, describe a Branch-and-Price algorithm and report some computational results.