reduction tests

A dual-ascent-based branch-and-bound framework for the prize-collecting Steiner tree and related problems

  • Markus Leitner
  • Ivana Ljubić
  • Martin Luipersbeck
  • Markus Sinnl
    • Categories Combinatorial Optimization, Integer Programming, Network Optimization Tags , , , ,

    In this work we present a branch-and-bound (B&B) framework for the asymmetric prize-collecting Steiner tree problem (APCSTP). Several well-known network design problems can be transformed to the APCSTP, including the Steiner tree problem (STP), prize-collecting Steiner tree problem (PCSTP), maximum-weight connected subgraph problem (MWCS) and the node-weighted Steiner tree problem (NWSTP). The main component of … Read more

    Reduction Tests for the Prize-Collecting Steiner Problem

  • Eduardo Uchoa
    • Categories Applications - OR and Management Sciences, Integer Programming, Telecommunications Tags , ,

    The Prize-Collecting Steiner Problem (PCSP) is a generalization of the classical Steiner Problem in Graphs (SPG) where instead of terminal vertices that must be necessarily connected, one have profits associated to the vertices that must be balanced against the connection costs. This problem is gaining much attention in the last years due to its practical … Read more