laminar family

A Simulated Annealing Algorithm for the Directed Steiner Tree Problem

  • Shabbir Ahmed
  • George L. Nemhauser
  • Matias Siebert
    • Categories Combinatorial Optimization, Dynamic Programming, Network Optimization Tags , , ,

    In \cite{siebert2019linear} the authors present a set of integer programs (IPs) for the Steiner tree problem, which can be used for both, the directed and the undirected setting of the problem. Each IP finds an optimal Steiner tree with a specific structure. A solution with the lowest cost, corresponds to an optimal solution to the … Read more

    A Linear Programming Based Approach to the Steiner Tree Problem with a Fixed Number of Terminals

  • Shabbir Ahmed
  • George L. Nemhauser
  • Matias Siebert
    • Categories Linear Programming, Network Optimization, Polyhedra Tags , , ,

    We present a set of integer programs (IPs) for the Steiner tree problem with the property that the best solution obtained by solving all, provides an optimal Steiner tree. Each IP is polynomial in the size of the underlying graph and our main result is that the linear programming (LP) relaxation of each IP is … Read more