IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v43y2022i5d10.1007_s10878-020-00690-1.html
   My bibliography  Save this article

Optimal Steiner trees under node and edge privacy conflicts

Author

Listed:
  • Alessandro Hill

    (California Polytechnic State University)

  • Roberto Baldacci

    (University of Bologna)

  • Stefan Voß

    (University of Hamburg)

Abstract

In this work, we suggest concepts and solution methodologies for a series of strategic network design problems that find application in highly data-sensitive industries, such as, for instance, the high-tech, governmental, or military sector. Our focus is on the installation of widely used cost-efficient tree-structured communication infrastructure. As base model we use the well-known Steiner tree problem, in which we are given terminal nodes, optional Steiner nodes, and potential network links between nodes. Its objective is to connect all terminals to a distributor node using a tree of minimum total edge costs. The novel, practically relevant side constraints are related to privacy concerns of customers, represented by terminals. In order to account for these, we study four privacy models that restrict the eligible infrastructure for the customer-distributor data exchange: (I) Selected pairs of terminals mutually exclude themselves as intermediate data-transmission nodes; (II) some pairs of terminals require disjoint paths to the distributor; (III) individual terminals forbid routing their data through allegedly untrustworthy links; and (IV) certain terminals do not allow the usage of doubtful links on their entire network branch. These topological data-privacy requirements significantly complicate the notoriously hard optimization problem. We clarify the model relationships by establishing dominance results, point out potential extensions and derive reduction tests. We present corresponding, strong non-compact integer programming (IP) formulations and embed these in efficient cutting plane methods. In addition, we develop constraint programming formulations that are used complementally to derive primal solutions. In a computational study, we analyze the performance of our methods on a diverse set of literature-based test instances.

Suggested Citation

  • Alessandro Hill & Roberto Baldacci & Stefan Voß, 2022. "Optimal Steiner trees under node and edge privacy conflicts," Journal of Combinatorial Optimization, Springer, vol. 43(5), pages 1509-1533, July.
    • Handle: RePEc:spr:jcomop:v:43:y:2022:i:5:d:10.1007_s10878-020-00690-1
    DOI: 10.1007/s10878-020-00690-1
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-020-00690-1
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-020-00690-1?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Sunil Chopra & Edgar R. Gorres & M. R. Rao, 1992. "Solving the Steiner Tree Problem on a Graph Using Branch and Cut," INFORMS Journal on Computing, INFORMS, vol. 4(3), pages 320-335, August.
    2. Filipecki, Bartosz & Van Vyve, Mathieu, 2020. "Stronger path-based extended formulation for the Steiner tree problem," LIDAM Reprints CORE 3129, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Yongjia Song & Minjiao Zhang, 2015. "Chance‐constrained multi‐terminal network design problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 62(4), pages 321-334, June.
    2. Laura Bahiense & Francisco Barahona & Oscar Porto, 2003. "Solving Steiner Tree Problems in Graphs with Lagrangian Relaxation," Journal of Combinatorial Optimization, Springer, vol. 7(3), pages 259-282, September.
    3. Aardal, K. & van Hoesel, C.P.M., 1995. "Polyhedral techniques in combinatorial optimization," Research Memorandum 014, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    4. Aardal, K.I. & van Hoesel, S., 1995. "Polyhedral Techniques in Combinatorial Optimization," Other publications TiSEM ed028a07-eb6a-4c8d-8f21-d, Tilburg University, School of Economics and Management.
    5. Rosenwein, Moshe B. & Wong, Richard T., 1995. "A constrained Steiner tree problem," European Journal of Operational Research, Elsevier, vol. 81(2), pages 430-439, March.
    6. Abilio Lucena & Nelson Maculan & Luidi Simonetti, 2010. "Reformulations and solution algorithms for the maximum leaf spanning tree problem," Computational Management Science, Springer, vol. 7(3), pages 289-311, July.
    7. Gollowitzer, Stefan & Gouveia, Luis & Ljubić, Ivana, 2013. "Enhanced formulations and branch-and-cut for the two level network design problem with transition facilities," European Journal of Operational Research, Elsevier, vol. 225(2), pages 211-222.
    8. Aardal, K.I. & van Hoesel, S., 1995. "Polyhedral Techniques in Combinatorial Optimization," Discussion Paper 1995-57, Tilburg University, Center for Economic Research.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jcomop:v:43:y:2022:i:5:d:10.1007_s10878-020-00690-1. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.