An Exact Algorithm for the Max-Min Covering Location Blocker Problem
Abstract
We introduce the Max-Min Covering Location Blocker Problem, a bilevel optimization problem in which a leader blocks a minimum-cost set of candidate locations so that the optimal coverage of a budget-constrained follower does not exceed a prescribed target. Each customer's coverage is determined by the least favorable open facility that can serve it. The induced follower coverage set function is nonmonotone and nonsubmodular, so the validity of interdiction cuts cannot be inherited from existing frameworks. We develop an exact nested decomposition that exploits the max-min coverage structure at both levels. At the outer level, we establish the validity of interdiction cuts from this structure and strengthen them with facility-specific coefficients bounding the coverage lost when a critical facility is removed. We solve the NP-hard follower problem by branch-and-Benders-cut after projecting out the customer coverage variables, and characterize an optimal dual solution of the separation problem in closed form, generating Benders optimality cuts in linear time without solving a linear program. Computational experiments on benchmark instances show that both ingredients substantially improve the performance of the method. With a moderate number of candidate locations, instances with 300,000 customers are solved to optimality within one hour. A comparison with two general-purpose bilevel solvers from the literature shows the proposed method to be one to three orders of magnitude faster, and to solve to optimality instances that neither of them closes. The model applies wherever the planner cannot control which facility serves a customer, as in public automated external defibrillator (AED) networks. A case study on a network using real AED data from Virginia Beach illustrates the model.
Related
- An exact algorithm for the pickup and delivery problem with time windows and requests split across multiple stacks
- An Exact Combinatorial Branch-and-Bound Algorithm for the Job Sequencing and Tool Switching Problem
- An Exact Branch-Price-and-Cut Algorithm for a Truck-as-Hub Vehicle Routing Problem with Drones
- The Exact Second Generalized Covering Radius of Binary Primitive Triple-Error-Correcting BCH Codes
- An exact hierarchy for Lebesgue's universal covering constant and a certified 0.834 lower bound
BibTeX
@misc{zhang2026exact,
title = {{An Exact Algorithm for the Max-Min Covering Location Blocker Problem}},
author = {Yun-Tian Zhang and Chen Chen and Fabio Furini and Ivana Ljubić},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.28084},
eprint = {2609.28084},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.28084},
}
RIS
TY - UNPB
TI - An Exact Algorithm for the Max-Min Covering Location Blocker Problem
AU - Yun-Tian Zhang
AU - Chen Chen
AU - Fabio Furini
AU - Ivana Ljubić
PY - 2026
DA - 2026/09/23
PB - arXiv
DO - 10.48550/arxiv.2609.28084
UR - https://arxiv.org/abs/2609.28084
AB - We introduce the Max-Min Covering Location Blocker Problem, a bilevel optimization problem in which a leader blocks a minimum-cost set of candidate locations so that the optimal coverage of a budget-constrained follower does not exceed a prescribed target. Each customer's coverage is determined by the least favorable open facility that can serve it. The induced follower coverage set function is nonmonotone and nonsubmodular, so the validity of interdiction cuts cannot be inherited from existing frameworks. We develop an exact nested decomposition that exploits the max-min coverage structure at both levels. At the outer level, we establish the validity of interdiction cuts from this structure and strengthen them with facility-specific coefficients bounding the coverage lost when a critical facility is removed. We solve the NP-hard follower problem by branch-and-Benders-cut after projecting out the customer coverage variables, and characterize an optimal dual solution of the separation problem in closed form, generating Benders optimality cuts in linear time without solving a linear program. Computational experiments on benchmark instances show that both ingredients substantially improve the performance of the method. With a moderate number of candidate locations, instances with 300,000 customers are solved to optimality within one hour. A comparison with two general-purpose bilevel solvers from the literature shows the proposed method to be one to three orders of magnitude faster, and to solve to optimality instances that neither of them closes. The model applies wherever the planner cannot control which facility serves a customer, as in public automated external defibrillator (AED) networks. A case study on a network using real AED data from Virginia Beach illustrates the model.
ER -