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 , 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.
Type de document :
Communication dans un congrès
International Symposium on Combinatorial Optimization (ISCO 2010), 2010, Hammamet, Tunisia. Elsevier, 36, pp.255-262, 2010, Electronic Notes in Discrete Mathematics. 〈10.1016/j.endm.2010.05.033〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00466485
Contributeur : Hervé Rivano <>
Soumis le : mercredi 24 mars 2010 - 00:31:57
Dernière modification le : lundi 4 décembre 2017 - 15:14:09

Identifiants

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. Elsevier, 36, pp.255-262, 2010, Electronic Notes in Discrete Mathematics. 〈10.1016/j.endm.2010.05.033〉. 〈inria-00466485〉

Partager

Métriques

Consultations de la notice

321