steiner trees

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

    Mathematical programming algorithms for spatial cloaking

  • Alberto Ceselli
  • Maria Luisa Damiani
  • Giovanni Righini
  • Diego Valorsi
    • Categories (Mixed) Integer Linear Programming, Applications - Science and Engineering, Combinatorial Optimization Tags , , ,

    We consider a combinatorial optimization problem for spatial information cloaking. The problem requires to compute one or several disjoint arborescences on a graph from a predetermined root or subset of candidate roots, so that the number of vertices in the arborescences is minimized but a given threshold on the overall weight associated with the vertices … Read more

    Local Search for Hop-constrained Directed Steiner Tree Problem with Application to UAV-based Multi-target Surveillance

  • Oleg Burdakov
  • Patrick Doherty
  • Jonas Kvarnström
    • Categories Applications - OR and Management Sciences, Multi-Criteria Optimization, Network Optimization Tags , , , ,

    We consider the directed Steiner tree problem (DSTP) with a constraint on the total number of arcs (hops) in the tree. This problem is known to be NP-hard, and therefore, only heuristics can be applied in the case of its large-scale instances. For the hop-constrained DSTP, we propose local search strategies aimed at improving any … Read more