Optimization Online


On imposing connectivity constraints in integer programs

Yiming Wang (kkelvin***at***tamu.edu)
Austin Buchanan (buchanan***at***tamu.edu)
Sergiy Butenko (butenko***at***tamu.edu)

Abstract: In many network applications, one searches for a connected subset of vertices that exhibits other desirable properties. To this end, this paper studies the connected subgraph polytope of a graph, which is the convex hull of subsets of vertices that induce a connected subgraph. Much of our work is devoted to the study of two nontrivial classes of valid inequalities. The first are the a,b-separator inequalities, which have been successfully used to enforce connectivity in previous computational studies. The second are the indegree inequalities, which have previously been shown to induce all nontrivial facets for trees. We determine the precise conditions under which these inequalities induce facets and when each class fully describes the connected subgraph polytope. Both classes of inequalities can be separated in polynomial time and admit compact extended formulations. However, while the a, b-separator inequalities can be lifted in linear time, it is NP-hard to lift the indegree inequalities.

Keywords: connected subgraph polytope; maximum-weight connected subgraph; connectivity constraints; prize-collecting Steiner tree; contiguity

Category 1: Combinatorial Optimization

Category 2: Combinatorial Optimization (Polyhedra )

Category 3: Network Optimization

Citation: Y. Wang, A. Buchanan, S. Butenko. On imposing connectivity constraints in integer programs. To appear, Mathematical Programming A, 2017. DOI: 10.1007/s10107-017-1117-8 http://link.springer.com/article/10.1007/s10107-017-1117-8


Entry Submitted: 02/02/2015
Entry Accepted: 02/04/2015
Entry Last Modified: 02/08/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society