  


On imposing connectivity constraints in integer programs
Yiming Wang (kkelvintamu.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,bseparator 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, bseparator inequalities can be lifted in linear time, it is NPhard to lift the indegree inequalities. Keywords: connected subgraph polytope; maximumweight connected subgraph; connectivity constraints; prizecollecting 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/s1010701711178 http://link.springer.com/article/10.1007/s1010701711178 Download: Entry Submitted: 02/02/2015 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  