Solving the Steiner Tree Problem on a Graph Using Branch and Cut

DOI10.1287/IJOC.4.3.320MaRDI QIDQ4030930zbMATH OpenOpenAlexFDO

Authors

Publication date 1 April 1993

Published in ORSA Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/ijoc.4.3.320

zbMATH Keywords

branch and cut solvercomplete graphsgrid graphsrandomly generated sparse graphsSteiner tree problem on a graph

Mathematics Subject Classification ID

Computational methods for problems pertaining to operations research and mathematical programming (90-08) Programming involving graphs or networks (90C35)

Recommendations

• Solving Steiner tree problems in graphs to optimality
• A branch and cut algorithm for the Steiner problem in graphs
• A Branch and Cut Algorithm for a Steiner Tree-Star Problem
• Solving Steiner tree problems in graphs with Lagrangian relaxation
• Steiner's problem in graphs: Heuristic methods

Cited in

(36)

• Using rank-1 lift-and-project closures to generate cuts for 0-1 MIPs, a computational investigation
• Combinatorial optimization in system configuration design
• A constrained Steiner tree problem
• The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
• Comparison of formulations and a heuristic for packing Steiner trees in a graph
• A robust and scalable algorithm for the Steiner problem in graphs
• Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm
• Thinning out Steiner trees: a node-based model for uniform edge costs
• Binary Steiner trees: structural results and an exact solution approach
• Generalized network design problems.
• On the core of the minimum cost Steiner tree game in networks
• Solving real-world linear ordering problems using a primal-dual interior point cutting plane method
• Optimal Steiner trees under node and edge privacy conflicts
• Stronger MIP formulations for the Steiner forest problem
• Heuristics and metaheuristics for accelerating the computation of simultaneous equations models through a Steiner tree
• Viral systems: A new bio-inspired optimisation approach
• An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
• Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut
• A branch and cut algorithm for the Steiner problem in graphs
• A branch-and-cut algorithm for solving generalized multiperiod Steiner problems in graphs
• Solving Steiner tree problems in graphs to optimality
• The Steiner tree problem with delays: a compact formulation and reduction procedures
• An Exact Algorithm for the Steiner Forest Problem
• Mathematical Programming Algorithms for Spatial Cloaking
• On the Minimal Steiner Tree Subproblem and Its Application in Branch-and-Price
• A Branch and Cut Algorithm for a Steiner Tree-Star Problem
• Improved algorithms for the Steiner problem in networks
• Approximation algorithms for Steiner forest: An experimental study
• An exact branch and bound algorithm for the Steiner Problem in Graphs
• Solving Steiner trees: Recent advances, challenges, and perspectives
• Optimizing the Design of a Wind Farm Collection Network
• Vertex covering with capacitated trees
• An extended formulation with valid inequalities for the capacitated Steiner arborescence problem
• The \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxation
• Mathematical methods for physical layout of printed circuit boards: an overview
• Reformulations and solution algorithms for the maximum leaf spanning tree problem

This page was built for publication: Solving the Steiner Tree Problem on a Graph Using Branch and Cut

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4030930)