Given a hypergraph @math , the Minimum Connectivity Inference problem asks for a graph on the same vertex set as @math with the minimum number of edges such that the subgraph induced by every hyperedge of @math is connected. This problem has received a lot of attention these recent years, both from a theoretical and practical perspective, leading to several implemented approximation, greedy and heuristic algorithms. Concerning exact algorithms, only Mixed Integer Linear Programming (MILP) formulations have been experimented, all representing connectivity constraints by the means of graph flows. In this work, we investigate the efficiency of a constraint generation algorithm, where we iteratively add cut constraints to a simple ILP until a feasible (and optimal) solution is found. It turns out that our method is faster than the previous best flow-based MILP algorithm on random generated instances, which suggests that a constraint generation approach might be also useful for other optimization problems dealing with connectivity constraints. At last, we present the results of an enumeration algorithm for the problem.
This MILP model was then improved recently by Dar al @cite_12 , who mainly reduced the number of variables and constraints of the formulation, but still representing the connectivity constraints by the means of flows. In addition, they also presented and implemented a number of (already known and new) reduction rules. This new MILP formulation together with the reduction rules were then compared to the algorithm of Agarwal al on randomly-generated instances. For every kind of tested hypergraphs (different number and sizes of hyperedges), they observed a drastic improvement of both the execution time and the maximum size of instances that could be solved.
@cite_12
2800207446
AbstractThe Minimum Connectivity Inference (MCI) problem represents an NP -hard generalization of the well-known minimum spanning tree problem and has been studied in different fields of research i...