  


Integer linear programming formulations for the minimum connectivity inference problem and model reduction principles
Muhammad Abid Dar(muhammad_abid.dartudresden.de) Abstract: The minimum connectivity inference (MCI) problem represents an NPhard generalization of the wellknown minimum spanning tree problem. Given a set of vertices and a finite collection of subsets (of this vertex set), the MCI problem requires to find an edge set of minimal cardinality so that the vertices of each subset are connected. Although the problem under consideration has appeared in different applicationoriented scientific contexts in the last decades, (efficient) approaches to its exact solution have hardly been addressed in the literature. Currently, even the most promising ILP formulation (an improved flowbased model) can only deal with rather small instances in reasonable times. In order to also tackle practically relevant problem sizes, our contribution is twofold: At first, we propose several new modelling frameworks for the MCI problem and investigate their theoretical properties as well as their computational behavior. Moreover, we introduce the concepts of simple model reduction and generalized model reduction which can be applied to reduce the numbers of variables and/or constraints in the various formulations. Based on extensive numerical experiments, the practical advantages of these principles are validated. Keywords: Minimum Connectivity Inference, Minimum Spanning Tree, MILP, Model Reduction, Polytopes Category 1: Integer Programming ((Mixed) Integer Linear Programming ) Category 2: Combinatorial Optimization (Polyhedra ) Citation: Preprint MATHNM032019, Technische Universität Dresden, 2019 Download: [PDF] Entry Submitted: 09/25/2019 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  