Optimization Online


Integer linear programming formulations for the minimum connectivity inference problem and model reduction principles

Muhammad Abid Dar(muhammad_abid.dar***at***tu-dresden.de)
Andreas Fischer(andreas.fischer***at***tu-dresden.de)
John Martinovic(john.martinovic***at***tu-dresden.de)
Guntram Scheithauer(guntram.scheithauer***at***tu-dresden.de)

Abstract: The minimum connectivity inference (MCI) problem represents an NP-hard generalization of the well-known 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 application-oriented 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 flow-based 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 MATH-NM-03-2019, Technische Universitšt Dresden, 2019

Download: [PDF]

Entry Submitted: 09/25/2019
Entry Accepted: 09/25/2019
Entry Last Modified: 09/25/2019

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