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
ULB - Université Libre de Bruxelles [Bruxelles], Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - 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 metadatas

https://hal.inria.fr/hal-01666308
Contributor : Markus Sinnl <>
Submitted on : Monday, December 18, 2017 - 11:13:14 AM
Last modification on : Tuesday, June 18, 2019 - 3:10:22 PM

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

177