Integer programming models for maximizing parallel transmissions in wireless networks
(2013) In Electronic Notes in Discrete Mathematics 41. p.197-204- Abstract
- In radio communications, a set of links that can transmit in parallel with a tolerable interference is called a compatible set. Finding a compatible set with maximum weighted revenue of the parallel transmissions is an important subproblem in wireless network management. For the subproblem, there are two basic approaches to express the signal to interference plus noise ratio (SINR) within integer programming, differing in the number of variables and the quality of the upper bound given by linear relaxations. To our knowledge, there is no systematic study comparing the effectiveness of the two approaches. The contribution of the paper is two-fold. Firstly, we present such a comparison, and, secondly, we introduce matching inequalities... (More)
- In radio communications, a set of links that can transmit in parallel with a tolerable interference is called a compatible set. Finding a compatible set with maximum weighted revenue of the parallel transmissions is an important subproblem in wireless network management. For the subproblem, there are two basic approaches to express the signal to interference plus noise ratio (SINR) within integer programming, differing in the number of variables and the quality of the upper bound given by linear relaxations. To our knowledge, there is no systematic study comparing the effectiveness of the two approaches. The contribution of the paper is two-fold. Firstly, we present such a comparison, and, secondly, we introduce matching inequalities improving the upper bounds as compared to the two basic approaches. The matching inequalities are generated within a branch-and-cut algorithm using a minimum odd-cut procedure based on the Gomory-Hu algorithm. The paper presents results of extensive numerical studies illustrating our statements and findings. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/5275880
- author
- Li, Yuan LU and Pioro, Michal LU
- organization
- publishing date
- 2013
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- branch-and-cut, matching polytope, Gomory-Hu algorithm, SINR
- in
- Electronic Notes in Discrete Mathematics
- volume
- 41
- pages
- 197 - 204
- publisher
- Elsevier
- external identifiers
-
- scopus:84879718312
- ISSN
- 1571-0653
- DOI
- 10.1016/j.endm.2013.05.093
- language
- English
- LU publication?
- yes
- id
- d1fba569-bbb9-452a-825b-34809e936e5d (old id 5275880)
- date added to LUP
- 2016-04-01 13:32:15
- date last changed
- 2022-01-27 19:42:02
@article{d1fba569-bbb9-452a-825b-34809e936e5d,
abstract = {{In radio communications, a set of links that can transmit in parallel with a tolerable interference is called a compatible set. Finding a compatible set with maximum weighted revenue of the parallel transmissions is an important subproblem in wireless network management. For the subproblem, there are two basic approaches to express the signal to interference plus noise ratio (SINR) within integer programming, differing in the number of variables and the quality of the upper bound given by linear relaxations. To our knowledge, there is no systematic study comparing the effectiveness of the two approaches. The contribution of the paper is two-fold. Firstly, we present such a comparison, and, secondly, we introduce matching inequalities improving the upper bounds as compared to the two basic approaches. The matching inequalities are generated within a branch-and-cut algorithm using a minimum odd-cut procedure based on the Gomory-Hu algorithm. The paper presents results of extensive numerical studies illustrating our statements and findings.}},
author = {{Li, Yuan and Pioro, Michal}},
issn = {{1571-0653}},
keywords = {{branch-and-cut; matching polytope; Gomory-Hu algorithm; SINR}},
language = {{eng}},
pages = {{197--204}},
publisher = {{Elsevier}},
series = {{Electronic Notes in Discrete Mathematics}},
title = {{Integer programming models for maximizing parallel transmissions in wireless networks}},
url = {{http://dx.doi.org/10.1016/j.endm.2013.05.093}},
doi = {{10.1016/j.endm.2013.05.093}},
volume = {{41}},
year = {{2013}},
}