Optimizing compatible sets in wireless networks through integer programming

Abstract

In wireless networks, the notion of compatible set refers to a set of radio links that can be simultaneously active with a tolerable interference. Finding a compatible set with maximum weighted revenue from the parallel transmissions is an important optimization subproblem for resource management in wireless networks. For this subproblem, two basic ways of expressing the signal-to-interference-plus-noise-ratio within integer programming are used, differing in the number of variables and the quality of the upper bound given by their linear relaxations. To our knowledge, there is no systematic study comparing the effectiveness of these two approaches to the compatible set optimization problem. The contribution of the article is twofold. First, we present a comparison of the two basic approaches, and, second, we introduce matching inequalities that improve the upper bounds achievable with the two basic approaches. The matching inequalities are generated within the branch-and-cut process using a minimum odd-cut generation procedure based on the Gomory–Hu tree algorithm. The article presents results of a numerical study illustrating our statements and findings.

Keywords

• 90C11 Mixed integer programming
• 90B18 Communication networks
• 68R10 Graph theory