Integer programming formulations for the shared multicast tree problem

Marika Ivanova () and Dag Haugland ()
Additional contact information
Marika Ivanova: University of Bergen
Dag Haugland: University of Bergen

Journal of Combinatorial Optimization, 2019, vol. 38, issue 3, No 16, 927-956

Abstract: Abstract We study the shared multicast tree (SMT) problem in wireless networks. To support a multicast session between a set of network nodes, SMT aims to establish a wireless connection between them, such that the total energy consumption is minimized. All destinations of the multicast message must be connected, while non-destinations are optional nodes that can be used to relay messages. The objective function reflecting power consumption distinguishes SMT clearly from the traditional minimum Steiner tree problem. We develop two integer programming formulations for SMT. Both models are subsequently extended and strengthened. Theorems on relations between the LP bounds corresponding to the models are stated and proved. As the number of variables in the strongest formulations is a polynomial of degree four in the number of network nodes, the models are impractical for computing lower bounds in instances beyond a fairly small size, and therefore a constraint generation scheme is developed. Results from computational experiments with the models demonstrate good promise of the approaches taken.

Keywords: Wireless communication; Multicast tree; Steiner tree; LP bound; Valid inequalities (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-019-00428-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:38:y:2019:i:3:d:10.1007_s10878-019-00428-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-019-00428-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().