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 a set of interfering links. It plays a central role in resource allocation, link scheduling or in finding achievable rate regions for both wireline and wireless networks. This problem is known to be NP-hard. We propose a solution method, based on the branch and bound technique, which solves globally the nonconvex WSRMax problem with an optimality certificate. Efficient analytic bounding techniques are introduced and their impact on the convergence is numerically evaluated. The considered link-interference model is general enough to model a wide range of network topologies with various node capabilities, e.g., single- or multipacket transmission (or reception), simultaneous transmission and reception. Several applications, including cross-layer network utility maximization and maximum weighted link scheduling for multihop wireless networks as well as finding achievable rate regions for singlecast/multicast wireless networks, are presented. 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.