Network Interdiction Goes Neural

dc.contributor.authorZhang, Leien
dc.contributor.authorChen, Zhiqianen
dc.contributor.authorLu, Chang-Tienen
dc.contributor.authorZhao, Liangen
dc.date.accessioned2025-09-10T12:23:39Zen
dc.date.available2025-09-10T12:23:39Zen
dc.date.issued2025-08-03en
dc.date.updated2025-09-01T07:47:53Zen
dc.description.abstractNetwork interdiction problems, arising in critical applications from military strategy to disease control, involve a complex attackerdefender dynamic: one player optimizes a network-based objective, while the other strategically modifies the network to impede that objective. The inherent bi-level optimization and combinatorial nature of these problems pose a significant computational challenge, often rendering traditional exact solvers impractical and hindering the development of effective heuristics. While Graph Neural Networks (GNNs) have demonstrated promise in solving singlelevel combinatorial optimization problems on graphs, their direct application to bi-level interdiction problems remains limited. In this paper, we bridge this gap by introducing a novel approach that leverages the power of GNNs to learn Mixed-Integer Linear Programming (MILP) formulations of network interdiction problems. By representing the problem in this structured mathematical form, we empower a multipartite GNN with the representational capacity to effectively capture the complex interplay between the two players. This approach aligns the neural network with the underlying mathematical structure of interdiction problems, leading to improved performance. Through extensive experiments on two network interdiction tasks, we demonstrate the superiority of our proposed method over both baseline GNN models and traditional exact solvers, showcasing its potential for real-world applications.en
dc.description.versionPublished versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.doihttps://doi.org/10.1145/3711896.3737063en
dc.identifier.urihttps://hdl.handle.net/10919/137727en
dc.language.isoenen
dc.publisherACMen
dc.rightsCreative Commons Attribution 4.0 Internationalen
dc.rights.holderThe author(s)en
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/en
dc.titleNetwork Interdiction Goes Neuralen
dc.typeArticle - Refereeden
dc.type.dcmitypeTexten

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
3711896.3737063.pdf
Size:
1.74 MB
Format:
Adobe Portable Document Format
Description:
Published version
License bundle
Now showing 1 - 1 of 1
Name:
license.txt
Size:
1.5 KB
Format:
Item-specific license agreed upon to submission
Description: