The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches
From MaRDI portal
Publication:2427392
DOI10.1007/s10589-007-9072-6zbMath1146.90082OpenAlexW2163625245MaRDI QIDQ2427392
Mohamed Haouari, Hanif D. Sherali, Safa Bhar Layeb
Publication date: 13 May 2008
Published in: Computational Optimization and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10589-007-9072-6
Programming involving graphs or networks (90C35) Derivative-free methods and methods using generalized derivatives (90C56)
Related Items
Strength of Three MIP Formulations for the Prize Collecting Steiner Tree Problem with a Quota Constraint, Lagrangian and branch-and-cut approaches for upgrading spanning tree problems, A relax-and-cut framework for large-scale maximum weight connected subgraph problems, Stabilizing branch‐and‐price for constrained tree problems, Lagrangian bounds for large‐scale multicommodity network design: a comparison between Volume and Bundle methods, Solving Steiner trees: Recent advances, challenges, and perspectives, Algorithmic expedients for the prize collecting Steiner tree problem, Optimal solution of the discrete cost multicommodity network design problem, Exact approaches for solving robust prize-collecting Steiner tree problems
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An O\((\log k)\)-approximation algorithm for the \(k\) minimum spanning tree problem in the plane
- A note on the prize collecting traveling salesman problem
- Upper and lower bounding strategies for the generalized minimum spanning tree problem
- Conjugate gradient methods using quasi-Newton updates with inexact line searches
- A primal-dual conjugate subgradient algorithm for specially structured linear and convex programming problems
- Integer programming approaches to facilities layout models with forbidden areas
- \(K\)-tree/\(K\)-subgraph: A program package for minimal weighted \(K\)-cardinlity trees and subgraphs
- Class Steiner trees and VLSI-design
- Variable metric bundle methods: From conceptual to implementable forms
- The volume algorithm revisited: relation with bundle methods
- Solving Steiner tree problems in graphs with Lagrangian relaxation
- Solving group Steiner problems as Steiner problems.
- An implementation of Shor's \(r\)-algorithm
- The volume algorithm: Producing primal solutions with a subgradient method
- Upper and lower bounding procedures for minimum rooted \(k\)-subtree problem
- The class Steiner minimal tree problem: A lower bound and test problem generation
- New metaheuristic approaches for the edge-weighted \(k\)-cardinality tree problem
- Local search algorithms for the \(k\)-cardinality tree problem.
- Strong lower bounds for the prize collecting Steiner problem in graphs
- A note on the generalized Steiner tree polytope
- A variable target value method for nondifferentiable optimization
- A hybrid Lagrangian genetic algorithm for the prize collecting Steiner tree problem
- Lagrangian duality applied to the vehicle routing problem with time windows
- An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
- An improved approximation scheme for the Group Steiner Problem
- Local search with perturbations for the prize-collecting Steiner tree problem in graphs
- A comparative analysis of several formulations for the generalized minimum spanning tree problem
- The Cutting-Plane Method for Solving Convex Programs
- Lagrangean decomposition: A model yielding stronger lagrangean bounds
- The node-weighted steiner tree problem
- An SST-based algorithm for the steiner problem in graphs
- The prize collecting traveling salesman problem
- An Efficient Primal Simplex Algorithm for Maximum Weighted Vertex Packing on Bipartite Graphs
- On convergence rates of subgradient optimization methods
- The B<scp>oxstep</scp> Method for Large-Scale Optimization
- An Algorithm for Constrained Optimization with Semismooth Functions
- Decomposing Matrices into Blocks
- Weighted k‐cardinality trees: Complexity and polyhedral structure
- Solving the generalized minimum spanning tree problem by a branch-and-bound algorithm
- Validation of subgradient optimization
- On the generalized minimum spanning tree problem
- Minimization of unsmooth functionals
- Convergence rate of the gradient descent method with dilatation of the space
- Limited memory space dilation and reduction algorithms
- Steiner tree problems
