Solving a Resource Allocation Problem in Wireless Mesh Networks: A Comparison Between a CP-Based and a Classical Column Generation

This article presents a column generation approach to a resource allocation problem arising in managing Wire- less Mesh Networks. The problem consists in routing the given demands over the network and to allocate time resource to pairs of nodes. Half-duplex constraints are taken into account together with the aggregate interfer- ence due to simultaneous transmissions, which affects the signal quality. Different problems are considered, according to the assumptions on the transmission power and rate. The resource allocation problem can be formu- lated as a Mixed Integer Linear Programming (MILP) prob- lem and dealt with a column generation-based approach. The pricing problem, due to signal quality constraints, turns out to be computationally demanding. To tackle these difficulties, besides a classical mathematical pro- gramming approach, we have applied a hybrid column generation approach where the pricing subproblem is solved using Constraint Programming. Numerical results show that the two methods are comparable. The results of the column generation are then used to solve heuristi- cally the problem. The obtained results provide very small gaps (between lower bounds and Heuristic solutions) for two of the three considered problems and reasonable gaps for the third problem.