Network Interdiction Goes Neural

Chang-Tien Lu; Lei Zhang; Liang Zhao; Zhiqian Chen

arxiv: 2405.16409 · v1 · submitted 2024-05-26 · 💻 cs.AI · cs.LG

Network Interdiction Goes Neural

Lei Zhang , Zhiqian Chen , Chang-Tien Lu , Liang Zhao This is my paper

Pith reviewed 2026-05-24 01:00 UTC · model grok-4.3

classification 💻 cs.AI cs.LG

keywords network interdictiongraph neural networkmixed-integer linear programmingbi-level optimizationcombinatorial optimizationattacker-defenderGNN for optimization

0 comments

The pith

A multipartite GNN learns MILP formulations to solve bi-level network interdiction problems.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper seeks to establish that bi-level network interdiction problems, where one agent alters a network to block another's optimization goal, can be converted into mixed-integer linear programming instances and then learned directly by a multipartite graph neural network. This matters because exact solvers scale poorly for applications such as military planning, epidemic control, and communication security, while prior neural methods handled only single-level graph problems. The multipartite GNN is chosen for its capacity to capture the structure of the MILP encoding, producing solutions that generalize past the training examples. If the approach holds, neural methods become compatible with the mathematical structure of these defender-attacker tasks rather than treating them as black-box graph tasks.

Core claim

By representing network interdiction problems as Mixed-Integer Linear Programming instances and applying a multipartite GNN with sufficient representational capacity to learn these formulations, the neural network becomes compatible with mathematical algorithms designed to solve network interdiction problems, resulting in improved generalization that outperforms theoretical baseline models and provides advantages over traditional exact solvers through two distinct tasks.

What carries the argument

multipartite GNN applied to MILP instances of bi-level network interdiction problems

If this is right

Solutions for attacker-defender problems become available at neural-network inference speeds rather than exact-solver runtimes.
GNN methods extend from single-level combinatorial tasks to bi-level optimization without losing compatibility with MILP theory.
The same learned model can be reused across multiple network instances instead of resolving each one from scratch.
Hybrid pipelines become feasible in which the GNN supplies candidate solutions that exact methods can verify or refine.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same multipartite-GNN-plus-MILP pattern may transfer to other bi-level problems such as facility location under disruption or supply-chain defense.
Training on a mixture of synthetic and real-world network topologies could reduce the distribution shift that currently limits generalization.
Because the GNN respects the MILP structure, its outputs could be fed directly into branch-and-bound solvers as warm starts.

Load-bearing premise

The multipartite GNN possesses enough representational capacity to learn MILP formulations of bi-level network interdiction problems in a way that generalizes beyond the training instances.

What would settle it

The trained model produces invalid or suboptimal interdiction decisions on networks whose size, density, or connectivity pattern lies outside the training distribution.

Figures

Figures reproduced from arXiv: 2405.16409 by Chang-Tien Lu, Lei Zhang, Liang Zhao, Zhiqian Chen.

**Figure 2.** Figure 2: Example Shortest Path Interdiction Instance [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

**Figure 3.** Figure 3: Averaged results visualization from 2,000 runs for each of the two methods. [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗

read the original abstract

Network interdiction problems are combinatorial optimization problems involving two players: one aims to solve an optimization problem on a network, while the other seeks to modify the network to thwart the first player's objectives. Such problems typically emerge in an attacker-defender context, encompassing areas such as military operations, disease spread analysis, and communication network management. The primary bottleneck in network interdiction arises from the high time complexity of using conventional exact solvers and the challenges associated with devising efficient heuristic solvers. GNNs, recognized as a cutting-edge methodology, have shown significant effectiveness in addressing single-level CO problems on graphs, such as the traveling salesman problem, graph matching, and graph edit distance. Nevertheless, network interdiction presents a bi-level optimization challenge, which current GNNs find difficult to manage. To address this gap, we represent network interdiction problems as Mixed-Integer Linear Programming (MILP) instances, then apply a multipartite GNN with sufficient representational capacity to learn these formulations. This approach ensures that our neural network is more compatible with the mathematical algorithms designed to solve network interdiction problems, resulting in improved generalization. Through two distinct tasks, we demonstrate that our proposed method outperforms theoretical baseline models and provides advantages over traditional exact solvers.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The multipartite GNN plus MILP encoding for bi-level interdiction is a reasonable extension of existing GNN solvers, but the abstract gives no numbers, datasets, or ablations to show it actually works or generalizes.

read the letter

The paper's main move is to cast network interdiction as MILP instances and run them through a multipartite GNN that is supposed to handle the bi-level structure better than standard single-level GNNs. That framing is new enough in the GNN-for-CO line of work, and it directly targets a setting where exact solvers are slow and single-level neural methods do not apply. The authors correctly note that interdiction shows up in security and network problems, so the target is practical. They also avoid claiming the GNN replaces the MILP solver entirely and instead position it as learning from the MILP formulation, which keeps the approach grounded rather than purely heuristic. That part is fine as far as it goes. The abstract does not cite prior identical work, so the specific multipartite architecture for this bi-level case appears to be their contribution. The stress-test concern about generalization is on target. The abstract asserts outperformance on two tasks and advantages over exact solvers, yet supplies no quantitative results, no instance sizes, no train-test split details, and no check that the model captures the nested min-max rather than just single-level graph statistics. Without those, it is impossible to know whether the multipartite design actually buys anything for the bi-level aspect or whether performance collapses when test graphs differ in size, density, or interdiction budget. The representational-capacity claim is stated but not isolated or tested in the provided text. This paper is aimed at people already working on neural solvers for combinatorial optimization who want to move into bi-level problems. A reader in that group could pick up the MILP-encoding idea and the multipartite architecture as a starting point. It is not ready for someone looking for a drop-in practical solver. The work deserves peer review because the underlying problem is real, the MILP framing is reproducible in principle, and the gap it tries to close is clear, even though the current evidence is too thin to judge the central claim.

Referee Report

2 major / 2 minor

Summary. The paper formulates network interdiction as bi-level MILP instances and proposes a multipartite GNN to learn these formulations, claiming that the approach yields better generalization than standard GNNs and outperforms both theoretical baselines and exact solvers on two distinct tasks.

Significance. If the empirical claims hold with proper controls for instance size, density, and budget shifts, the work would provide a concrete bridge between GNN representational capacity and bi-level combinatorial optimization, potentially enabling faster heuristics for attacker-defender problems in security and infrastructure domains.

major comments (2)

[Abstract] Abstract: the central claim that the multipartite GNN 'ensures ... improved generalization' and 'outperforms theoretical baseline models' is asserted without any quantitative metrics, error bars, dataset sizes, train/test split details, or ablation isolating the multipartite structure from ordinary graph features; this prevents verification that the nested min-max structure is actually learned rather than single-level graph statistics.
[Introduction / Method (GNN representational capacity paragraph)] The load-bearing assumption that the multipartite GNN possesses sufficient capacity to generalize the MILP encoding of bi-level interdiction beyond the training distribution (different sizes, densities, or interdiction budgets) is stated but not supported by any derivation, capacity argument, or controlled experiment that varies the test distribution while holding the multipartite architecture fixed.

minor comments (2)

[Abstract] The abstract refers to 'two distinct tasks' without naming them or indicating whether they are synthetic or real-world network instances.
[Abstract] Notation for the multipartite GNN layers and how they encode the leader-follower variables of the MILP is not introduced in the provided abstract; a short table or diagram would clarify compatibility with the mathematical algorithms mentioned.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive and detailed feedback. We address each major comment point by point below and commit to revisions that strengthen the empirical support and clarity of the claims.

read point-by-point responses

Referee: [Abstract] Abstract: the central claim that the multipartite GNN 'ensures ... improved generalization' and 'outperforms theoretical baseline models' is asserted without any quantitative metrics, error bars, dataset sizes, train/test split details, or ablation isolating the multipartite structure from ordinary graph features; this prevents verification that the nested min-max structure is actually learned rather than single-level graph statistics.

Authors: We agree that the abstract presents the claims in qualitative terms only. The full manuscript reports quantitative results, including performance metrics with error bars, dataset sizes, train/test splits, and ablations comparing the multipartite structure against standard GNNs in the experimental sections. To address the concern directly, we will revise the abstract to include specific numerical results, details on the experimental protocol, and reference to the ablation isolating the multipartite design, thereby making the support for learning the bi-level MILP structure explicit. revision: yes
Referee: [Introduction / Method (GNN representational capacity paragraph)] The load-bearing assumption that the multipartite GNN possesses sufficient capacity to generalize the MILP encoding of bi-level interdiction beyond the training distribution (different sizes, densities, or interdiction budgets) is stated but not supported by any derivation, capacity argument, or controlled experiment that varies the test distribution while holding the multipartite architecture fixed.

Authors: The manuscript provides empirical results across two tasks that include instances of varying sizes and densities, demonstrating outperformance relative to baselines. However, we acknowledge that a formal capacity derivation is absent and that the existing experiments do not isolate distribution shifts in a dedicated controlled manner while holding the architecture fixed. We will add a new controlled-experiment subsection that systematically varies test-set sizes, densities, and budgets while freezing the multipartite GNN, to furnish direct evidence for the generalization claim. revision: yes

Circularity Check

0 steps flagged

No significant circularity; empirical learning of MILP formulations is self-contained.

full rationale

The paper represents network interdiction problems as MILP instances and applies a multipartite GNN to learn the formulations, claiming outperformance on two tasks versus baselines and exact solvers. No equations, fitted parameters renamed as predictions, or self-citation chains are present that reduce any claimed result to its inputs by construction. The representational capacity assertion is an empirical hypothesis about generalization, not a definitional or fitted-input loop. The approach is a standard ML application to combinatorial optimization and remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the domain assumption that network interdiction problems admit MILP encodings and that multipartite GNNs can learn those encodings at sufficient capacity; no free parameters or invented entities are mentioned in the abstract.

axioms (2)

domain assumption Network interdiction problems can be represented as MILP instances
Stated directly in the abstract as the first modeling step.
domain assumption Multipartite GNNs possess sufficient representational capacity for these MILP formulations
Invoked to justify why the architecture can handle bi-level problems that standard GNNs cannot.

pith-pipeline@v0.9.0 · 5742 in / 1304 out tokens · 24791 ms · 2026-05-24T01:00:41.808133+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

[1]

Learning-based efficient graph similarity computation via multi-scale convolutional set matching

Yunsheng Bai, Hao Ding, Ken Gu, Yizhou Sun, and Wei Wang. Learning-based efficient graph similarity computation via multi-scale convolutional set matching. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 3219–3226, 2020

work page 2020
[2]

Maher, Frederic Matter, Erik Mühmer, Benjamin Müller, Marc E

Ksenia Bestuzheva, Mathieu Besançon, Wei-Kun Chen, Antonia Chmiela, Tim Donkiewicz, Jasper van Doornmalen, Leon Eifler, Oliver Gaul, Gerald Gamrath, Ambros Gleixner, Leona Gottwald, Christoph Graczyk, Katrin Halbig, Alexander Hoen, Christopher Hojny, Rolf van der Hulst, Thorsten Koch, Marco Lübbecke, Stephen J. Maher, Frederic Matter, Erik Mühmer, Benjami...

work page 2021
[3]

What’s wrong with deep learning in tree search for combinatorial optimization

Maximilian Böther, Otto Kißig, Martin Taraz, Sarel Cohen, Karen Seidel, and Tobias Friedrich. What’s wrong with deep learning in tree search for combinatorial optimization. arXiv preprint arXiv:2201.10494, 2022

work page arXiv 2022
[4]

Khalil, Andrea Lodi, Christopher Morris, and Petar Veliˇckovi´c

Quentin Cappart, Didier Chételat, Elias B. Khalil, Andrea Lodi, Christopher Morris, and Petar Veliˇckovi´c. Combinatorial optimization and reasoning with graph neural networks. In Zhi-Hua Zhou, editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21 , pages 4348–4355. International Joint Conferences on Ar- ...

work page doi:10.24963/ijcai.2021/595 2021
[6]

On representing linear programs by graph neural networks

Ziang Chen, Jialin Liu, Xinshang Wang, and Wotao Yin. On representing linear programs by graph neural networks. In The Eleventh International Conference on Learning Representations, 2022

work page 2022
[7]

Introduction to algorithms

Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2022

work page 2022
[8]

Computational methods for deterministic and stochastic network interdiction problems

Kelly J Cormican. Computational methods for deterministic and stochastic network interdiction problems. Technical report, NA V AL POSTGRADUATE SCHOOL MONTEREY CA, 1995

work page 1995
[9]

Handbook of Combinatorial Optimization: Supplement Volume A, volume 1

Ding-Zhu Du and Panos M Pardalos. Handbook of Combinatorial Optimization: Supplement Volume A, volume 1. Springer Science & Business Media, 2013

work page 2013
[10]

Graph neural networks are dynamic programmers

Andrew J Dudzik and Petar Veliˇckovi´c. Graph neural networks are dynamic programmers. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 20635–20647. Curran Associates, Inc., 2022. URL https://proceedings.neurips.cc/paper_files/paper/2022/file/ 8248b1ded388fcd...

work page 2022
[11]

M. Fey, J. E. Lenssen, C. Morris, J. Masci, and N. M. Kriege. Deep graph matching consensus. In International Conference on Learning Representations (ICLR), 2020

work page 2020
[12]

Exact combinatorial optimization with graph convolutional neural networks

Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. Advances in neural information processing systems, 32, 2019

work page 2019
[13]

A gnn-guided predict-and-search framework for mixed-integer linear programming

Qingyu Han, Linxin Yang, Qian Chen, Xiang Zhou, Dong Zhang, Akang Wang, Ruoyu Sun, and Xiaodong Luo. A gnn-guided predict-and-search framework for mixed-integer linear programming. In The Eleventh International Conference on Learning Representations, 2022

work page 2022
[14]

A GNN-guided predict-and-search framework for mixed-integer linear programming

Qingyu Han, Linxin Yang, Qian Chen, Xiang Zhou, Dong Zhang, Akang Wang, Ruoyu Sun, and Xiaodong Luo. A GNN-guided predict-and-search framework for mixed-integer linear programming. In The Eleventh International Conference on Learning Representations, 2023. URL https://openreview.net/forum?id=pHMpgT5xWaE. 11

work page 2023
[15]

An efficient graph convolutional network technique for the travelling salesman problem.arXiv preprint arXiv:1906.01227, 2019

Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.01227, 2019

work page arXiv 1906
[16]

Kipf and Max Welling

Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations , 2017. URL https: //openreview.net/forum?id=SJU4ayYgl

work page 2017
[17]

Graph matching networks for learning the similarity of graph structured objects

Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching networks for learning the similarity of graph structured objects. In International conference on machine learning, pages 3835–3845. PMLR, 2019

work page 2019
[18]

Combinatorial optimization with graph convolu- tional networks and guided tree search

Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolu- tional networks and guided tree search. Advances in neural information processing systems, 31, 2018

work page 2018
[19]

Solving mixed integer programs using neural networks

Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid V on Glehn, Pawel Lichocki, Ivan Lobov, Brendan O’Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, et al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012.13349, 2020

work page arXiv 2012
[20]

Learning to solve np-complete problems: A graph neural network for decision tsp

Marcelo Prates, Pedro HC Avelar, Henrique Lemos, Luis C Lamb, and Moshe Y Vardi. Learning to solve np-complete problems: A graph neural network for decision tsp. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4731–4738, 2019

work page 2019
[21]

Ecole: A gym-like library for machine learning in combinatorial optimization solvers

Antoine Prouvost, Justin Dumouchelle, Lara Scavuzzo, Maxime Gasse, Didier Chételat, and Andrea Lodi. Ecole: A gym-like library for machine learning in combinatorial optimization solvers. In Learning Meets Combinatorial Algorithms at NeurIPS2020, 2020. URL https: //openreview.net/forum?id=IVc9hqgibyB

work page 2020
[22]

Random features strengthen graph neural networks

Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM international conference on data mining (SDM), pages 333–341. SIAM, 2021

work page 2021
[23]

Luca E Schäfer. GitHub - Luca-Elias-Schaefer/Gurobi-Models: In this project, one can find an extensive collection of classical optimization problems along with a proposed solution procedure using Gurobi. — github.com. https://github.com/Luca-Elias-Schaefer/ Gurobi-Models, 2021. [Accessed 21-05-2024]

work page 2021
[24]

A survey of network interdiction models and algorithms

J Cole Smith and Yongjia Song. A survey of network interdiction models and algorithms. European Journal of Operational Research, 283(3):797–811, 2020

work page 2020
[25]

Deterministic network interdiction

R Kevin Wood. Deterministic network interdiction. Mathematical and Computer Modelling, 17 (2):1–18, 1993

work page 1993
[26]

How powerful are graph neural networks? In International Conference on Learning Representations , 2019

Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations , 2019. URL https: //openreview.net/forum?id=ryGs6iA5Km

work page 2019
[27]

Du, Ken ichi Kawarabayashi, and Stefanie Jegelka

Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S. Du, Ken ichi Kawarabayashi, and Stefanie Jegelka. What can neural networks reason about? In International Conference on Learning Representations, 2020. URL https://openreview.net/forum?id=rJxbJeHFPS. 12 A Proofs for Section 4 Our approach to measuring the representation power of MMILP-GNN is heavily inspired b...

work page 2020

[1] [1]

Learning-based efficient graph similarity computation via multi-scale convolutional set matching

Yunsheng Bai, Hao Ding, Ken Gu, Yizhou Sun, and Wei Wang. Learning-based efficient graph similarity computation via multi-scale convolutional set matching. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 3219–3226, 2020

work page 2020

[2] [2]

Maher, Frederic Matter, Erik Mühmer, Benjamin Müller, Marc E

Ksenia Bestuzheva, Mathieu Besançon, Wei-Kun Chen, Antonia Chmiela, Tim Donkiewicz, Jasper van Doornmalen, Leon Eifler, Oliver Gaul, Gerald Gamrath, Ambros Gleixner, Leona Gottwald, Christoph Graczyk, Katrin Halbig, Alexander Hoen, Christopher Hojny, Rolf van der Hulst, Thorsten Koch, Marco Lübbecke, Stephen J. Maher, Frederic Matter, Erik Mühmer, Benjami...

work page 2021

[3] [3]

What’s wrong with deep learning in tree search for combinatorial optimization

Maximilian Böther, Otto Kißig, Martin Taraz, Sarel Cohen, Karen Seidel, and Tobias Friedrich. What’s wrong with deep learning in tree search for combinatorial optimization. arXiv preprint arXiv:2201.10494, 2022

work page arXiv 2022

[4] [4]

Khalil, Andrea Lodi, Christopher Morris, and Petar Veliˇckovi´c

Quentin Cappart, Didier Chételat, Elias B. Khalil, Andrea Lodi, Christopher Morris, and Petar Veliˇckovi´c. Combinatorial optimization and reasoning with graph neural networks. In Zhi-Hua Zhou, editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21 , pages 4348–4355. International Joint Conferences on Ar- ...

work page doi:10.24963/ijcai.2021/595 2021

[5] [6]

On representing linear programs by graph neural networks

Ziang Chen, Jialin Liu, Xinshang Wang, and Wotao Yin. On representing linear programs by graph neural networks. In The Eleventh International Conference on Learning Representations, 2022

work page 2022

[6] [7]

Introduction to algorithms

Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2022

work page 2022

[7] [8]

Computational methods for deterministic and stochastic network interdiction problems

Kelly J Cormican. Computational methods for deterministic and stochastic network interdiction problems. Technical report, NA V AL POSTGRADUATE SCHOOL MONTEREY CA, 1995

work page 1995

[8] [9]

Handbook of Combinatorial Optimization: Supplement Volume A, volume 1

Ding-Zhu Du and Panos M Pardalos. Handbook of Combinatorial Optimization: Supplement Volume A, volume 1. Springer Science & Business Media, 2013

work page 2013

[9] [10]

Graph neural networks are dynamic programmers

Andrew J Dudzik and Petar Veliˇckovi´c. Graph neural networks are dynamic programmers. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 20635–20647. Curran Associates, Inc., 2022. URL https://proceedings.neurips.cc/paper_files/paper/2022/file/ 8248b1ded388fcd...

work page 2022

[10] [11]

M. Fey, J. E. Lenssen, C. Morris, J. Masci, and N. M. Kriege. Deep graph matching consensus. In International Conference on Learning Representations (ICLR), 2020

work page 2020

[11] [12]

Exact combinatorial optimization with graph convolutional neural networks

Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. Advances in neural information processing systems, 32, 2019

work page 2019

[12] [13]

A gnn-guided predict-and-search framework for mixed-integer linear programming

Qingyu Han, Linxin Yang, Qian Chen, Xiang Zhou, Dong Zhang, Akang Wang, Ruoyu Sun, and Xiaodong Luo. A gnn-guided predict-and-search framework for mixed-integer linear programming. In The Eleventh International Conference on Learning Representations, 2022

work page 2022

[13] [14]

A GNN-guided predict-and-search framework for mixed-integer linear programming

Qingyu Han, Linxin Yang, Qian Chen, Xiang Zhou, Dong Zhang, Akang Wang, Ruoyu Sun, and Xiaodong Luo. A GNN-guided predict-and-search framework for mixed-integer linear programming. In The Eleventh International Conference on Learning Representations, 2023. URL https://openreview.net/forum?id=pHMpgT5xWaE. 11

work page 2023

[14] [15]

An efficient graph convolutional network technique for the travelling salesman problem.arXiv preprint arXiv:1906.01227, 2019

Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.01227, 2019

work page arXiv 1906

[15] [16]

Kipf and Max Welling

Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations , 2017. URL https: //openreview.net/forum?id=SJU4ayYgl

work page 2017

[16] [17]

Graph matching networks for learning the similarity of graph structured objects

Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching networks for learning the similarity of graph structured objects. In International conference on machine learning, pages 3835–3845. PMLR, 2019

work page 2019

[17] [18]

Combinatorial optimization with graph convolu- tional networks and guided tree search

Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolu- tional networks and guided tree search. Advances in neural information processing systems, 31, 2018

work page 2018

[18] [19]

Solving mixed integer programs using neural networks

Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid V on Glehn, Pawel Lichocki, Ivan Lobov, Brendan O’Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, et al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012.13349, 2020

work page arXiv 2012

[19] [20]

Learning to solve np-complete problems: A graph neural network for decision tsp

Marcelo Prates, Pedro HC Avelar, Henrique Lemos, Luis C Lamb, and Moshe Y Vardi. Learning to solve np-complete problems: A graph neural network for decision tsp. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4731–4738, 2019

work page 2019

[20] [21]

Ecole: A gym-like library for machine learning in combinatorial optimization solvers

Antoine Prouvost, Justin Dumouchelle, Lara Scavuzzo, Maxime Gasse, Didier Chételat, and Andrea Lodi. Ecole: A gym-like library for machine learning in combinatorial optimization solvers. In Learning Meets Combinatorial Algorithms at NeurIPS2020, 2020. URL https: //openreview.net/forum?id=IVc9hqgibyB

work page 2020

[21] [22]

Random features strengthen graph neural networks

Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM international conference on data mining (SDM), pages 333–341. SIAM, 2021

work page 2021

[22] [23]

Luca E Schäfer. GitHub - Luca-Elias-Schaefer/Gurobi-Models: In this project, one can find an extensive collection of classical optimization problems along with a proposed solution procedure using Gurobi. — github.com. https://github.com/Luca-Elias-Schaefer/ Gurobi-Models, 2021. [Accessed 21-05-2024]

work page 2021

[23] [24]

A survey of network interdiction models and algorithms

J Cole Smith and Yongjia Song. A survey of network interdiction models and algorithms. European Journal of Operational Research, 283(3):797–811, 2020

work page 2020

[24] [25]

Deterministic network interdiction

R Kevin Wood. Deterministic network interdiction. Mathematical and Computer Modelling, 17 (2):1–18, 1993

work page 1993

[25] [26]

How powerful are graph neural networks? In International Conference on Learning Representations , 2019

Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations , 2019. URL https: //openreview.net/forum?id=ryGs6iA5Km

work page 2019

[26] [27]

Du, Ken ichi Kawarabayashi, and Stefanie Jegelka

Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S. Du, Ken ichi Kawarabayashi, and Stefanie Jegelka. What can neural networks reason about? In International Conference on Learning Representations, 2020. URL https://openreview.net/forum?id=rJxbJeHFPS. 12 A Proofs for Section 4 Our approach to measuring the representation power of MMILP-GNN is heavily inspired b...

work page 2020