Search papers, labs, and topics across Lattice.
This paper introduces a Dual-Agent Deep Reinforcement Learning (DADRL) framework to solve the Maximal Covering Location-Interdiction Problem (MCLIP), a bi-level optimization challenge in resilient infrastructure planning. The framework uses adversarial training, with a location agent maximizing coverage and an interdiction agent minimizing it, to capture the dynamic interplay between the two levels. A Surrogate-based Ensemble Inference Strategy further leverages the interdiction agent to guide the location agent, achieving superior computational efficiency and competitive solution quality on both synthetic and real-world datasets.
Adversarial training with deep reinforcement learning cracks the computationally intractable Maximal Covering Location-Interdiction Problem, outperforming traditional methods in speed and solution quality.
The Maximal Covering Location-Interdiction Problem (MCLIP) is a classic bi-level optimization problem, which is fundamental to resilient infrastructure planning yet remains computationally intractable. Specifically, the upper level determines facility locations to maximize coverage, while the lower level executes worst-case interdiction to minimize the coverage. The strong coupling between the upper and lower levels, combined with their respective high combinatorial complexity, renders traditional methods ineffective. To bridge this gap, we propose a Dual-Agent Deep Reinforcement Learning (DADRL) framework based on adversarial learning, comprising a location agent corresponding to the upper level and an interdiction agent corresponding to the lower level. Our contributions are threefold: (1) The location agent is trained simultaneously against an evolving interdiction agent, making it effectively capture the dynamic competitive interplay between the upper and lower levels; (2) To fully exploit the learned capabilities of the interdiction agent, we propose a Surrogate-based Ensemble Inference Strategy that utilizes the trained interdiction agent as a high-fidelity surrogate to guide the decisions of location agent; (3) Extensive experiments on synthetic and real-world datasets demonstrate that our approach achieves superior computational efficiency while maintaining highly competitive solution quality compared to other baselines. Furthermore, our DADRL framework is model-agnostic to network structures, while its underlying adversarial learning paradigm demonstrates strong potential for solving other bi-level optimization problems.
