Integer Programming Models For Maximizing Parallel Transmissions In Wireless Networks

Yuan Li , Michał Pióro


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 Yuan Li - [Lunds Universitet]
Yuan Li,,
, Michał Pióro (FEIT / IT)
Michał Pióro,,
- The Institute of Telecommunications
Journal seriesElectronic Notes in Discrete Mathematics, [Electron Notes Discrete Math], ISSN 1571-0653
Issue year2013
Publication size in sheets0.5
Conference6th International Network Optimization Conference (INOC 2013), 20-05-2013 - 22-05-2013, Tenerife, Hiszpania
Keywords in Englishbranch-and-cut, matching polytope, Gomory-Hu algorithm, SINR.
ASJC Classification2604 Applied Mathematics; 2607 Discrete Mathematics and Combinatorics
ProjectMixed-integer programming models for joint optimization of link capacity assignment, flow scheduling, and routing in fair multicommodity flow networks. Project leader: Pióro Michał, , Phone: +48 22 234-7383, application date 07-06-2011, start date 07-12-2011, end date 06-12-2014, IT/2012/badawczy/30, Completed
WEiTI Projects financed by NSC [Projekty finansowane przez NCN]
The Develpment of Digital Communicatios. Project leader: Lubacz Józef, , Phone: 22 234 65 31, start date 04-05-2012, planned end date 31-03-2013, end date 31-12-2013, IT/2012/statut, Completed
WEiTI Działalność statutowa
Languageen angielski
Li Pióro Integer programming 2013.pdf 209.15 KB
Score (nominal)15
Score sourceconferenceIndex
ScoreMinisterial score = 10.0, 17-03-2020, ArticleFromJournalAndMatConfByIndicator
Ministerial score (2013-2016) = 15.0, 17-03-2020, ArticleFromJournalAndMatConfByIndicator
Publication indicators Scopus Citations = 0; Scopus SNIP (Source Normalised Impact per Paper): 2013 = 0.476
Citation count*
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Are you sure?