Connectivity is a central concept in combinatorial optimization, graph theory, and operations research. In many applications, one is interested in finding an optimal subset of vertices with the essential requirement that the vertices are connected, but not how they are connected. I.e., it is not relevant, which edges are selected to obtain connectivity. Two natural examples in this category are the maximum-weight connected subgraph problem (MWCSP) and the uniform weight (prize-collecting) Steiner tree problem. This article is concerned with the exact solution of such problems via integer programming. On the theoretical side, we analyze and compare IP and MIP formulations with respect to the strength of their LP relaxations. Along the way, we also provide a tighter (compact) description of the connected subgraph polytope-the convex hull of subsets of vertices that induce a connected subgraph. Furthermore, we give a (compact) complete description of the connected subgraph polytope for graphs with no four independent vertices. On the algorithmic side, we introduce new components, such as primal and dual heuristics, to enhance a branch-and-cut algorithm based on the strongest previously considered IP formulation. These developments allow us to solve MWCSP benchmark instances from the literature faster than current state-of-the-art solvers. Additionally, previously intractable instances can be solved to optimality.
Article
View Optimal Connected Subgraphs: Formulations and Algorithms