Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem

DOI10.1137/17M1145963zbMath1410.90130MaRDI QIDQ4620424

Daniel Rehfeldt, Thorsten Koch

Publication date: 8 February 2019

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

zbMATH Keywords

combinatorial optimizationreduction techniquesmaximum-weight connected subgraph problem

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Related Items

Imposing Contiguity Constraints in Political Districting Models, On the Exact Solution of Prize-Collecting Steiner Tree Problems, New formulations and branch-and-cut procedures for the longest induced path problem, Optimal connected subgraphs: Integer programming formulations and polyhedra, Maximum weighted induced forests and trees: new formulations and a computational comparative review, Solving Steiner trees: Recent advances, challenges, and perspectives, Vertex covering with capacitated trees, Mixed-integer programming techniques for the connected max-\(k\)-cut problem

Uses Software

• SCIP
• SteinLib
• SCIP-Jack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polyhedral study of the connected subgraph problem
• A robust and scalable algorithm for the Steiner problem in graphs
• On imposing connectivity constraints in integer programs
• Thinning out Steiner trees: a node-based model for uniform edge costs
• SCIP-Jack -- a solver for STP and variants with parallelization extensions
• Solving generalized maximum-weight connected subgraph problem for network enrichment analysis
• A data structure for dynamic trees
• Reduction tests for the prize-collecting Steiner problem
• Conflict analysis in mixed integer programming
• Algorithms for the Maximum Weight Connected $$k$$-Induced Subgraph Problem
• A dual ascent approach for steiner tree problems on a directed graph
• Solving Connected Subgraph Problems in Wildlife Conservation
• Solving Steiner tree problems in graphs to optimality
• Transformations for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem to SAP
• The Rooted Maximum Node-Weight Connected Subgraph Problem
• A Dual Ascent-Based Branch-and-Bound Framework for the Prize-Collecting Steiner Tree and Related Problems
• The Maximum Weight Connected Subgraph Problem
• Efficient Greedy Heuristics For Steiner Tree Problems Using Reolptimization And Super Modularity
• The NP-completeness column: An ongoing guide
• Improved algorithms for the Steiner problem in networks