INFORMS Best Paper 2022 awarded to Alessandro Hill, Roberto Baldacci and Stefan Voß

28 October 2022, by Julia Bachale

Photo: Informs

During the INFORMS 2022 Annual Meeting, tanking place from October 16 to 19 in Indianapolis, US; the 2022 INFORMS Best Paper Award was awarded to Alessandro Hill (California Polytechnic State University), Roberto Baldacci ( Hamad Bin Khalifa University) and Stefan Voß (IWI) for their paper "Optimal Steiner Trees under Node and Edge Privacy Conflicts".

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.