A relax-and-cut framework for large-scale maximum weight connected subgraph problems

DOI10.1016/j.cor.2017.05.015zbMath1391.90595OpenAlexW2618313358WikidataQ126130209 ScholiaQ126130209MaRDI QIDQ1652399

Eduardo Álvarez-Miranda, Markus Sinnl

Publication date: 11 July 2018

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2017.05.015

zbMATH Keywords

bioinformaticsLagrangian pelaxationmaximum weight connected subgraph problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Systems biology, networks (92C42)

Related Items (5)

Method of the Joint Clustering in Network and Correlation Spaces ⋮ Imposing Contiguity Constraints in Political Districting Models ⋮ On approximating maximum covering cycles in undirected graphs ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ Vertex covering with capacitated trees

Uses Software

• Knapsack
• igraph
• DIMACS
• BioNet

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Primal-dual subgradient methods for convex problems
• A facet generation and relaxation technique applied to an assignment problem with side constraints
• Non delayed relax-and-cut algorithms
• Conjugate gradient methods using quasi-Newton updates with inexact line searches
• Two ``well-known properties of subgradient optimization
• A relax-and-cut algorithm for the prize-collecting Steiner problem in graphs
• Efficient cuts in Lagrangean `relax-and-cut' schemes
• A Lagrangian relax-and-cut approach for the sequential ordering problem with precedence relationships
• A Lagrangian relax-and-cut approach for the two-stage capacitated facility location problem
• A divide and conquer matheuristic algorithm for the prize-collecting Steiner tree problem
• On imposing connectivity constraints in integer programs
• Algorithmic expedients for the prize collecting Steiner tree problem
• The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches
• Recovery of primal solutions when using subgradient optimization methods to solve Lagrangian duals of linear programs
• An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
• Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
• Solving Connected Subgraph Problems in Wildlife Conservation
• A strong lower bound for the Node Weighted Steiner Tree Problem
• A node‐based ILP formulation for the node‐weighted dominating Steiner problem
• Optimal rectangular partitions
• The Rooted Maximum Node-Weight Connected Subgraph Problem
• Imposing Connectivity Constraints in Forest Planning Models
• The Maximum Weight Connected Subgraph Problem
• Lagrangian Relaxation via Ballstep Subgradient Methods

This page was built for publication: A relax-and-cut framework for large-scale maximum weight connected subgraph problems