Optimization Online


An Improved Flow-based Formulation and Reduction Principles for the Minimum Connectivity Inference Problem

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 generalisation of the well-known minimum spanning tree problem and has been studied in different fields of research independently. Let an undirected complete graph and finitely many subsets (clusters) of its vertex set be given. Then, the MCI problem is to find a minimal subset of edges so that every cluster is connected with respect to this minimal subset. Whereas, in general, existing approaches can only be applied to find approximate solutions or optimal edge sets of rather small instances, concepts to optimally cope with more meaningful problem sizes have not been proposed yet in literature. For this reason, we present a new mixed integer linear programming formulation for the MCI problem, and introduce new instance reduction methods that can be applied to downsize the complexity of a given instance prior to the optimisation. Based on theoretical and computational results both contributions are shown to be beneficial for solving larger instances.

Keywords: Minimum connectivity inference, reduction rules, mixed integer linear programming model, subset interconnection design

Category 1: Combinatorial Optimization

Category 2: Integer Programming

Category 3: Applications -- Science and Engineering

Citation: Optimization, https://doi.org/10.1080/02331934.2018.1465944 Technical Report: MATH-NM-05-2017, Institute of Numerical Mathematics, Faculty of Mathematics, TU Dresden, Germany, October 2017

Download: [PDF]

Entry Submitted: 04/27/2018
Entry Accepted: 05/01/2018
Entry Last Modified: 06/08/2018

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