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.
Type de document :
Article dans une revue
Computers & Operations Research, 2017, 87, pp.63 - 82. 〈10.1016/j.cor.2017.05.015〉
Liste complète des métadonnées

Contributeur : Markus Sinnl <>
Soumis le : lundi 18 décembre 2017 - 11:13:14
Dernière modification le : vendredi 13 avril 2018 - 01:28:51




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



Consultations de la notice