Presolving for spatially large general backup covering location problem with applications to urban security monitoring

Covering location problems have received considerable attention in spatial optimization, exemplified by applications such as urban security monitoring. While current optimization techniques are effective at small to moderate scales, advances in multi-source spatial big data and geospatial analytics toolkit compel us to address spatially large problems. Unlike traditional approaches relying on coarse demand aggregation, these fine-grained spatial problems involve millions to tens of millions of demand points. In this paper, we focus on a general backup covering location problem involving heterogeneous, anisotropic devices in a 3-D environment. Recognizing that this NP-hard problem becomes computationally intractable at such scales, we exploit the spatial features and supply–demand relationships to develop efficient, problem-specific spatial reduction strategies, collectively referred to as presolving. These strategies drastically reduce the number of decision variables and constraints while preserving optimality. Extensive computational experiments demonstrate theoretical rigor and practical viability on synthetic problem instances and a real world case study in Beijing, China. Thanks to the proposed presolving techniques, optimal solutions can be obtained rapidly for these instances involving up to 20 million demand points, which are previously considered unsolvable.