A node‐based ILP formulation for the node‐weighted dominating Steiner problem | doi.page

0 citations0 references

A node‐based ILP formulation for the node‐weighted dominating Steiner problem

Networks2016Vol. 69(1), pp. 33–51

Citations Over TimeTop 24% of 2016 papers

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

Citations Over TimeTop 24% of 2016 papers

Abstract

Related Papers