Weighted sum-rate maximization for a set of interfering links via branch and bound

We consider the problem of weighted sum-rate maximization (WSRMax) for an arbitrary set of interfering links. This problem is known to be NP-hard; therefore, it is extremely difficult to solve even for a relative small number of links. The main contribution of this paper is to provide a solution method, based on the branch and bound technique, which solves WSRMax problem with an optimality certificate. At each step of the proposed algorithm, an upper and a lower bound are computed for the optimal value of the underlying problem. The algorithm terminates when the difference between the upper and the lower bound is smaller than a specified tolerance. The proposed algorithm can be further used to provide other performance benchmarks by back-substituting it into any network design method which relies on WSRMax. It is also very useful for evaluating the performance loss encountered by any heuristic algorithm.