Integer Programming Formulations for the Shared Multicast Tree Problem

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.