Exact approaches for solving robust prize-collecting Steiner tree problems

DOI10.1016/j.ejor.2013.03.037zbMath1317.90300OpenAlexW2118486696WikidataQ62048279 ScholiaQ62048279MaRDI QIDQ2355891

Eduardo Álvarez-Miranda, Ivana Ljubić, Paolo Toth

Publication date: 28 July 2015

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2013.03.037

zbMATH Keywords

mixed integer programmingrobust optimizationbranch-and-cutinterval uncertaintyprize collecting Steiner trees

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Heuristics for the network design problem with connectivity requirements, Solving Steiner trees: Recent advances, challenges, and perspectives, Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree

Uses Software

• SteinLib

Cites Work

• Unnamed Item
• A note on the prize collecting traveling salesman problem
• A new model for path planning with interval data
• A relax-and-cut algorithm for the prize-collecting Steiner problem in graphs
• On implementing the push-relabel method for the maximum flow problem
• Robust discrete optimization and network flows
• Adjustable robust solutions of uncertain linear programs
• Strong lower bounds for the prize collecting Steiner problem in graphs
• A survey and annotated bibliography of multiobjective combinatorial optimization
• Algorithmic expedients for the prize collecting Steiner tree problem
• Cutting plane versus compact formulations for uncertain (integer) linear programs
• The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches
• A note on the Bertsimas \& Sim algorithm for robust combinatorial optimization problems
• Reduction tests for the prize-collecting Steiner problem
• A hybrid Lagrangian genetic algorithm for the prize collecting Steiner tree problem
• An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
• Locating leak detecting sensors in a water distribution network by solving prize-collecting Steiner arborescence problems
• Local search with perturbations for the prize-collecting Steiner tree problem in graphs
• Cover inequalities for robust knapsack sets-Application to the robust bandwidth packing problem
• Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP
• Efficient Algorithms for the Prize Collecting Steiner Tree Problems with Interval Data
• The Price of Robustness
• The node-weighted steiner tree problem
• The prize collecting traveling salesman problem
• Solving Steiner tree problems in graphs to optimality
• Technical Note—Branch-and-Price-and-Cut Approach to the Robust Network Design Problem Without Flow Bifurcations
• Algorithms - ESA 2003