The Maximum Weight Connected Subgraph Problem
The Maximum (Node-) Weight Connected Subgraph Problem (MWCS) searches for a connected subgraph with maximum total weight in a node-weighted (di)graph. In this work we introduce a new integer linear programming formulation built on node variables only, whi
- PDF / 481,151 Bytes
- 26 Pages / 441 x 666 pts Page_size
- 83 Downloads / 217 Views
Abstract The Maximum (Node-) Weight Connected Subgraph Problem (MWCS) searches for a connected subgraph with maximum total weight in a node-weighted (di)graph. In this work we introduce a new integer linear programming formulation built on node variables only, which uses new constraints based on node-separators. We theoretically compare its strength to previously used MIP models in the literature and study the connected subgraph polytope associated with our new formulation. In our computational study we compare branch-and-cut implementations of the new model with two models recently proposed in the literature: one of them using the transformation into the Prize-Collecting Steiner Tree problem, and the other one working on the space of node variables only. The obtained results indicate that the new formulation outperforms the previous ones in terms of the running time and in terms of the stability with respect to variations of node weights.
1 Introduction The Maximum (Node-) Weight Connected Subgraph Problem (MWCS) is the problem of finding a connected subgraph with maximum total weight in a node-weighted (di)graph. It belongs to the class of network design problems and has applications
E. Álvarez-Miranda Dipartimento di Ingegneria dell’Energia Elettrica e dell’Informazione, Università di Bologna, Viale Risorgimento 2, 40136 Bologna, Italy e-mail: [email protected] I. Ljubi´c (B) Institut für Statistik und Operations Research, Universität Wien, Brünnerstraße 72, 1210 Vienna, Austria e-mail: [email protected] P. Mutzel Fakultät für Informatik, Technische Universität Dortmund, Otto-Hahn-Straße 14, 44227 Dortmund, Germany e-mail: [email protected] M. Jünger, G. Reinelt (eds.), Facets of Combinatorial Optimization, DOI 10.1007/978-3-642-38189-8_11, © Springer-Verlag Berlin Heidelberg 2013
245
246
E. Álvarez-Miranda, I. Ljubi´c, and P. Mutzel
in various different areas such as forestry, wildlife preservation planning, systems biology, computer vision, and communication network design. Lee and Dooly [23] introduced a cardinality-constrained version of the problem for building a designed fiber-optic communication network over time, where the given node weights reflect their degree of importance. They defined the maximumweight connected graph problem for an undirected graph with given node weights, in which they search the connected subgraph of maximum weight consisting of exactly a predescribed number of nodes. The same problem version was considered already in [18] (the authors called it Connected k-Subgraph Problem) for a Norwegian off-shore oil-drilling application. Another application arises in the area of systems biology [1, 8, 26]. Yamamoto et al. [26] suggest the cardinality-constrained MWCS in order to detect core source components in gene networks, which seem to be responsible for the difference between normal cells and mutant cells. The input graphs are constructed from gene regulation networks combined with gene expression data provided as node weights. Maximum weight connected subgraphs
Data Loading...
