A node‐based ILP formulation for the node‐weighted dominating Steiner problem. Issue 1 (25th November 2016)

• Record Type: Journal Article
• Authors: Bley, Andreas; Ljubić, Ivana; Maurer, Olaf
• Is Part Of: Networks. Volume 69:Issue 1(2017)
• Page Start: 33
• Page End: 51
• Publication Date: 2016-11-25
• Subjects: connected dominating set -- Steiner tree -- integer programming -- thin formulation -- polyhedron -- facets; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21722
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract : In this article, we consider the Node‐Weighted Dominating Steiner Problem. Given a graph with node weights and a set of terminal nodes, the goal is to find a connected node‐induced subgraph of minimum weight, such that each terminal node is contained in or adjacent to some node in the chosen subgraph. The problem arises in applications in the design of telecommunication networks. Integer programming formulations for Steiner problems usually employ a variable for each edge. We introduce a formulation that only uses node variables and that models connectivity through node‐cut inequalities, which can be separated in polynomial time. We discuss necessary and sufficient conditions for the model inequalities to define facets and we introduce a class of lifted partition‐based inequalities, which can be used to strengthen the linear relaxation. Finally, we show that the polyhedron defined by these inequalities is integral if the underlying graph is a cycle where no two terminals are adjacent. In the general cycle setting, we show that we can get a complete description of the feasible solutions by lifting and projecting into a polytope with no more than twice the dimension. We also show that the well‐known indegree equalities are implied by the lifted partition inequalities. Finally, we evaluate the effectiveness of the presented partition inequalities in computational experiments. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 69(1), 33–51 2017