Cross Line and Column Generation for the Cut Covering Problem in Wireless Networks

Christelle Caillouet 1 Stéphane Pérennes 2 Hervé Rivano 3
1 Drakkar
LIG - Laboratoire d'Informatique de Grenoble
2 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
3 SWING - Smart Wireless Networking
Inria Grenoble - Rhône-Alpes, CITI - CITI Centre of Innovation in Telecommunications and Integration of services
Abstract : In this paper, we address the problem of bandwidth allocation and routing in wireless networks. A first model of this problem is known as the Round Weighting Problem (RWP) in which a weight is assigned to the set of rounds, i.e. a set of pairwise non-interfering links. We present a new formulation that forgets about the routing and concentrate on the capacity available on the network cuts. We use the maximum flow/minimum cut theorem known in graph theory to develop the Cut Covering Problem (CCP) and prove that it computes equivalent optimal round weights than RWP. We develop a primal/dual algorithm combining line and column generation to deal with the exponential number of variables and constraints of CCP.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/inria-00466485
Contributor : Hervé Rivano <>
Submitted on : Wednesday, March 24, 2010 - 12:31:57 AM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM

Identifiers

Citation

Christelle Caillouet, Stéphane Pérennes, Hervé Rivano. Cross Line and Column Generation for the Cut Covering Problem in Wireless Networks. International Symposium on Combinatorial Optimization (ISCO 2010), 2010, Hammamet, Tunisia. pp.255-262, ⟨10.1016/j.endm.2010.05.033⟩. ⟨inria-00466485⟩

Share

Metrics

Record views

515