A systematic study of the delayed column generation method for optimizing wireless networks
Yu Cheng, Xianghui Cao, Xuemin Shen, Devu Manikantan Shila, Hongkun Li · 2014
The main-thread approach for optimizing the throughput capacity over a multihop wireless network is to apply a multi-commodity flow (MCF) formulation, augmented with a scheduling constraint derived from the conflict graph associated with the network. A fundamental issue with the conflict graph based MCF formulation is that finding all independent sets (ISs) for scheduling is NP-hard in general. If we express the MCF formulation in a matrix format, the constraint matrix will contain a very large number of columns, with each IS being associated with one column. According to the linear programming theorem, such a type of problem can be addressed with the delayed column generation (DCG) method. Unfortunately, applications of the DCG in wireless networks have not received much attention. To the best of knowledge, none of the existing work conducted theoretical studies of the performance of DCG in wireless networks. In this paper, we study the DCG method in the context of a general network flow problem. With a protocol interference model, we rigorously prove that searching an entering column in the DCG operation is equivalent to a maximum weighted independent set (MWIS) problem. A prominent theoretical contribution of this paper is the theorem that: if an MWIS approximation algorithm with the approximation ratio β (<1) is applied in the DCG method, the maximum flow solved will be at least β of the optimal solution. Furthermore, the DCG method is also applied to the multi-radio multi-channel (MR-MC) networks. With extensive numerical results comparing to the existing methods, we show that the DCG method achieves the most preferred tradeoff between computation complexity and network capacity and maintains good scalability when addressing large-scale networks, particularly in the complex MR-MC context.