Skip to Main content Skip to Navigation
Journal articles

A Relax-and-Cut framework for large-scale maximum weight connected subgraph problems

Eduardo Álvarez-Miranda 1 Markus Sinnl 2, 3
2 INOCS - Integrated Optimization with Complex Structure
Inria Lille - Nord Europe, ULB - Université libre de Bruxelles, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
Abstract : Finding maximum weight connected subgraphs within networks is a fundamental combinatorial optimization problem both from theoretical and practical standpoints. One of the most prominent applications of this problem appears in Systems Biology and it corresponds to the detection of active subnetworks within gene interaction networks. Due to its importance, several modeling and algorithmic strategies have been proposed for tackling the maximum weight connected subgraph problem (MWCS) over the last years; the most effective strategies typically depend on the use of integer linear programming (ILP). Nonetheless, this implies that large-scale networks (such as those appearing in Systems Biology) can become burdensome; moreover, not all practitioners may have access to an ILP solver. In this paper, a unified modeling and algorithmic scheme is designed to solve the MWCS and some of its application-oriented variants with cardinality-constraints or budget-constraints. The proposed framework is based on a general node-based model which is tackled by a Relax-and-Cut scheme, i.e., Lagrangian relaxation combined with constraint generation; this yields a heuristic procedure capable of providing both dual and primal bounds. The approach is enhanced by additional valid inequalities, lifted valid inequalities, primal heuristics and variable-fixing procedures. Computational results on instances from the literature, as well as on additional large-scale instances, show that the proposed framework is competitive with respect to the existing approaches and it allows to find improved solutions for some unsolved instances from literature. The effect of initializing a Branch-and-Cut approach with information from the Relax-and-Cut is also investigated. The implemented approach is made available online.
Document type :
Journal articles
Complete list of metadata
Contributor : Markus Sinnl Connect in order to contact the contributor
Submitted on : Monday, December 18, 2017 - 11:13:14 AM
Last modification on : Tuesday, August 24, 2021 - 4:52:08 PM




Eduardo Álvarez-Miranda, Markus Sinnl. A Relax-and-Cut framework for large-scale maximum weight connected subgraph problems. Computers and Operations Research, Elsevier, 2017, 87, pp.63 - 82. ⟨10.1016/j.cor.2017.05.015⟩. ⟨hal-01666308⟩



Record views