Mathematical programming for locating essential services in unreliable trees
Modern infrastructures require resilience against network disruptions. Reliable Facility Location addresses these uncertainties, ensuring system robustness despite component failures in sectors like telecommunications or emergency services. We focus on the p-Maximum Expected Covering Problem (p-MECUN), aiming to locate p facilities in an undirected network with independent edge failures. Given a scenario of operational and failed edges, a node is said to be covered if it remains reachable from at least one server via functional edges; the goal of the p-MECUN is to maximize the expected number of covered nodes.
In this work, we restrict the problem to cases where the underlying network is a tree. For this type of networks, we propose a general quadratic programming formulation and a specialized linear version for a particular case. Comparisons with state-of-the-art algorithms demonstrate that our formulations efficiently provide optimal solutions.
Keywords: Discrete location reliability