Pith. sign in

REVIEW 2 major objections 2 minor 25 references

Necessary and sufficient conditions tie submodularity or supermodularity of defender objectives in network interdiction solely to attack locations.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.3

2026-06-27 12:38 UTC pith:BRK4XG6A

load-bearing objection The paper derives necessary and sufficient conditions for submodularity and supermodularity of the defender's value function in several network interdiction problems, depending only on attack locations. the 2 major comments →

arxiv 2606.10345 v1 pith:BRK4XG6A submitted 2026-06-09 math.OC

Supermodularity and Submodularity in Network Interdiction

Bo Zhou , Ruiwei Jiang , Siqian Shen This is my paper
classification math.OC
keywords network interdictionsubmodularitysupermodularitybilevel optimizationmin-cost flowmaximum flowshortest path
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper derives necessary and sufficient conditions under which the defender's optimal objective becomes submodular or supermodular as a function of the attacker's interdiction decisions. These conditions apply to three attack types in min-cost flow problems and extend to capacitated facility location, maximum flow, and shortest path interdiction. They hold for general network topologies and arbitrary parameters, depending only on attack locations. The resulting properties generate valid inequalities that accelerate solution of the bilevel integer program. Readers would care because the structure converts an otherwise intractable combinatorial problem into one amenable to faster exact methods.

Core claim

In the min-cost flow interdiction problem the defender's optimal objective is supermodular or submodular with respect to the set of interdicted components if and only if the interdictions meet explicit location conditions for each attack type; the same location criteria carry over to facility location, maximum flow, and shortest path interdiction and continue to hold when the defender is allowed extra binary decisions such as repairs or reinforcements.

What carries the argument

Location-based conditions that make the defender's optimal value a submodular or supermodular set function of the attacked components.

Load-bearing premise

The defender's optimal objective satisfies submodularity or supermodularity solely as a function of attack locations under arbitrary network topologies and parameter values.

What would settle it

A concrete network instance in which attacks at locations meeting the stated conditions produce an objective value that is neither submodular nor supermodular.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Valid inequalities derived from the submodularity or supermodularity properties accelerate exact solution of the bilevel integer program.
  • The location conditions apply directly to capacitated facility location interdiction, maximum flow interdiction, and shortest path interdiction.
  • Less restrictive conditions suffice for shortest path and maximum flow interdiction on series-parallel networks.
  • Submodularity is preserved or supermodularity recovered when the defender can make additional binary decisions such as repairing or reinforcing attacked components.

Where Pith is reading between the lines

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

  • The location conditions could be checked before optimization to decide whether submodular techniques will apply to a given instance.
  • Sequential attacks in multi-stage settings might permit dynamic programming when each stage satisfies the location criteria.
  • Network operators could prioritize protection of components whose interdiction would break the identified conditions.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 2 minor

Summary. The manuscript examines bilevel network interdiction problems and derives necessary and sufficient conditions under which the defender's optimal objective value is submodular or supermodular in the attacker's interdiction decisions. For min-cost flow interdiction, conditions are given for three attack types (on supplies/demands, capacities, and costs) that depend only on attack locations and are claimed to hold for arbitrary network topologies and parameters. Extensions cover maximum-flow, shortest-path, and capacitated facility-location interdiction, as well as variants in which the defender makes additional binary decisions; further results are stated for series-parallel networks. Numerical experiments are presented to illustrate order-of-magnitude speed-ups obtained by exploiting the identified properties to generate valid inequalities.

Significance. If the stated necessary-and-sufficient conditions are correctly established, the work supplies structural properties that can be used to strengthen formulations or invoke specialized submodular optimization routines, thereby improving scalability of interdiction models in infrastructure-protection and logistics applications. The location-only dependence (independent of numerical parameter values) would be a notable technical contribution if rigorously shown for general topologies.

major comments (2)
  1. [§3] §3 (MinCF capacity-attack case): the necessity direction of the claimed condition is shown by constructing a pair of attack sets whose marginal costs violate submodularity when the condition fails, but the sufficiency argument only verifies the inequality for pairs of attacks that differ by a single element; an explicit check that the property extends to arbitrary finite sets (via the standard submodular-set-function characterization) is missing and is load-bearing for the general-topology claim.
  2. [§5.2] §5.2 (defender binary decisions): the recovery of supermodularity after adding repair variables is asserted to hold under a location-based condition, yet the proof sketch replaces the original defender problem with a modified one whose feasible region depends on the attack set; it is not shown that this replacement preserves the exact optimal value for every attack set, which is required for the supermodularity claim to carry over.
minor comments (2)
  1. The numerical section reports speed-ups but does not list the MIP solver, tolerance settings, or hardware used; adding these details would allow readers to reproduce the reported order-of-magnitude gains.
  2. [§2] Notation for the attack indicator vector x and the defender's optimal value v(x) is introduced in §2 but is occasionally reused with different meanings in the series-parallel section; a single consistent definition table would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address each major comment below.

read point-by-point responses

  1. Referee: [§3] §3 (MinCF capacity-attack case): the necessity direction of the claimed condition is shown by constructing a pair of attack sets whose marginal costs violate submodularity when the condition fails, but the sufficiency argument only verifies the inequality for pairs of attacks that differ by a single element; an explicit check that the property extends to arbitrary finite sets (via the standard submodular-set-function characterization) is missing and is load-bearing for the general-topology claim.

    Authors: We thank the referee for this observation. The sufficiency argument relies on verifying the diminishing-returns inequality, which is equivalent to the full submodular-set-function definition. To strengthen the presentation and make the extension to arbitrary finite sets fully explicit, we will add a short paragraph in the revised §3 confirming the equivalence and, if appropriate, including a brief inductive verification. This clarification does not alter the conditions or claims but addresses the concern for general topologies. revision: yes

  2. Referee: [§5.2] §5.2 (defender binary decisions): the recovery of supermodularity after adding repair variables is asserted to hold under a location-based condition, yet the proof sketch replaces the original defender problem with a modified one whose feasible region depends on the attack set; it is not shown that this replacement preserves the exact optimal value for every attack set, which is required for the supermodularity claim to carry over.

    Authors: We agree that the proof sketch in §5.2 requires additional detail on this point. In the revision we will expand the argument to explicitly demonstrate that, under the stated location-based condition, the modified defender problem has the same optimal value as the original problem for every attack set. This will rigorously justify that supermodularity carries over. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper derives necessary and sufficient conditions for submodularity and supermodularity of the defender's optimal value function with respect to attack locations in bilevel network interdiction problems (MinCF, MaxF, SP, facility location). These are presented as structural properties obtained directly from the bilevel formulations under general topologies and parameters, without any indication of parameter fitting, renaming of known results, or load-bearing self-citations that reduce the claims to prior unverified assertions by the same authors. The conditions are stated to depend solely on attack locations, and numerical studies serve as empirical validation rather than the source of the derivations. No step in the provided abstract or scoping reduces by construction to an input via self-definition or fitted prediction.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review supplies no explicit free parameters, axioms, or invented entities; all claims concern structural properties derived from standard bilevel optimization formulations.

pith-pipeline@v0.9.1-grok · 5798 in / 1221 out tokens · 25144 ms · 2026-06-27T12:38:07.396373+00:00 · methodology

0 comments
read the original abstract

We study a bilevel network interdiction problem, with an attacker interdicting (attacking) certain components of a network and a defender optimizing operations over the ensuing network. We study when the defender's optimal objective is submodular or supermodular with respect to the attacker's interdiction decisions, for optimizing the bilevel integer program more efficiently. We first consider the min-cost flow (MinCF) interdiction problem and derive necessary and sufficient conditions for the supermodularity or submodularity to hold under three types of attacks, respectively on supplies/demands, flow capacities, and cost coefficients. We extend to other variants, including capacitated facility location, maximum flow (MaxF), and shortest path (SP) interdiction. The conditions hold under general network topologies and parameter settings, and depend solely on the locations of the attacks. We further incorporate additional network information (e.g., detailed parameters and special topologies) to establish less restrictive conditions. We also derive necessary and sufficient conditions for supermodularity or submodularity in SP and MaxF interdiction in series-parallel networks. Furthermore, we explore more challenging interdiction problems where the defender may make additional binary decisions (e.g., repairing or reinforcing the network) and identify conditions that preserve submodularity or recover supermodularity. Via extensive numerical studies with diverse types of attacks, we demonstrate an order-of-magnitude computational speedup achieved by exploiting these properties and generating valid inequalities, for solving network interdiction at scale.

Figures

Figures reproduced from arXiv: 2606.10345 by Bo Zhou, Ruiwei Jiang, Siqian Shen.

Figure 1
Figure 1. Figure 1: Difference between Theorem 1 (left) and Theorem 2 (right). [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Topological relationship with respect to paths. [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Topological relationship with respect to [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Transformation from attacks on flow capacities to attacks on cost coefficients. [PITH_FULL_IMAGE:figures/full_fig_p011_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Transformation from attacks on supplies/demands to attacks on cost coefficients. [PITH_FULL_IMAGE:figures/full_fig_p012_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Topological relationship with respect to cycles. [PITH_FULL_IMAGE:figures/full_fig_p014_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Topological relationship after removing redundant arcs. [PITH_FULL_IMAGE:figures/full_fig_p020_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: (b), respectively. (a) Supermodular (b) Submodular [PITH_FULL_IMAGE:figures/full_fig_p021_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Examples for MaxF interdiction in SPNs [PITH_FULL_IMAGE:figures/full_fig_p023_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Transformation from repairs to attacks. Remark 2. We note that the intuition shown in [PITH_FULL_IMAGE:figures/full_fig_p025_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Comparison in MinCF interdiction with attacks on nodes. [PITH_FULL_IMAGE:figures/full_fig_p028_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Comparison in MaxF interdiction with attacks on arcs. [PITH_FULL_IMAGE:figures/full_fig_p030_12.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

25 extracted references · 1 canonical work pages

  1. [1]

    Algorithms for network interdiction and fortification games

    J Cole Smith and Churlzu Lim. Algorithms for network interdiction and fortification games. InPareto optimality, game theory and equilibria, pages 609–644. Springer, 2008

    2008

  2. [2]

    Shortest-path network interdiction.Networks, 40(2):97–111, 2002

    Eitan Israeli and R Kevin Wood. Shortest-path network interdiction.Networks, 40(2):97–111, 2002

    2002

  3. [3]

    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. 30

    2020

  4. [4]

    Learning to solve bilevel programs with binary ten- der

    Bo Zhou, Ruiwei Jiang, and Siqian Shen. Learning to solve bilevel programs with binary ten- der. InProceedings of the 12th International Conference on Learning Representation (ICLR), Vienna, Austria, May 2024

    2024

  5. [5]

    A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation.Mathematical Programming Computation, 12(4):529–568, 2020

    Sahar Tahernejad, Ted K Ralphs, and Scott T DeNegre. A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation.Mathematical Programming Computation, 12(4):529–568, 2020

    2020

  6. [6]

    Bilevel mixed-integer linear program with binary tender.arXiv:2509.02370, 2025

    Bo Zhou, Ruiwei Jiang, and Siqian Shen. Bilevel mixed-integer linear program with binary tender.arXiv:2509.02370, 2025

    work page arXiv 2025

  7. [7]

    A branch-and-cut algorithm for submodular interdiction games.INFORMS Journal on Computing, 34(5):2634–2657, 2022

    Kubra Taninmis and Markus Sinnl. A branch-and-cut algorithm for submodular interdiction games.INFORMS Journal on Computing, 34(5):2634–2657, 2022

    2022

  8. [8]

    An analysis of approxi- mations for maximizing submodular set functions-I.Mathematical programming, 14:265–294, 1978

    George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approxi- mations for maximizing submodular set functions-I.Mathematical programming, 14:265–294, 1978

    1978

  9. [9]

    Springer, 2003

    Alexander Schrijver et al.Combinatorial optimization: Polyhedra and efficiency, volume 24. Springer, 2003

    2003

  10. [10]

    Submodularity in conic quadratic mixed 0–1 optimization

    Alper Atamt¨ urk and Andr´ es G´ omez. Submodularity in conic quadratic mixed 0–1 optimization. Operations Research, 68(2):609–630, 2020

    2020

  11. [11]

    The submodular knapsack polytope.Discrete Opti- mization, 6(4):333–344, 2009

    Alper Atamt¨ urk and Vishnu Narayanan. The submodular knapsack polytope.Discrete Opti- mization, 6(4):333–344, 2009

    2009

  12. [12]

    Ambiguous chance-constrained binary programs under mean-covariance information.SIAM Journal on Optimization, 28(4):2922–2944, 2018

    Yiling Zhang, Ruiwei Jiang, and Siqian Shen. Ambiguous chance-constrained binary programs under mean-covariance information.SIAM Journal on Optimization, 28(4):2922–2944, 2018

    2018

  13. [13]

    Outer approximation and submodular cuts for maximum capture facility location problems with random utilities.European Journal of Operational Research, 266(1):46–56, 2018

    Ivana Ljubi´ c and Eduardo Moreno. Outer approximation and submodular cuts for maximum capture facility location problems with random utilities.European Journal of Operational Research, 266(1):46–56, 2018

    2018

  14. [14]

    Sequential competitive facility location: Exact and approximate algorithms.Operations Research, 72(1):300–316, 2024

    Mingyao Qi, Ruiwei Jiang, and Siqian Shen. Sequential competitive facility location: Exact and approximate algorithms.Operations Research, 72(1):300–316, 2024

    2024

  15. [15]

    Submodular functions, matroids, and certain polyhedra

    Jack Edmonds. Submodular functions, matroids, and certain polyhedra. InCombinatorial Optimization – Eureka, You Shrink!, pages 11–26. Springer, 2003

    2003

  16. [16]

    Maximizing submodular set functions: Formu- lations and analysis of algorithms.Studies on Graphs and Discrete Programming, 11:279–301, 1981

    George L Nemhauser and Laurence A Wolsey. Maximizing submodular set functions: Formu- lations and analysis of algorithms.Studies on Graphs and Discrete Programming, 11:279–301, 1981

    1981

  17. [17]

    Substitutes and complements in network flow problems

    David Gale and Themistocles Politof. Substitutes and complements in network flow problems. Discrete Applied Mathematics, 3(3):175–186, 1981

    1981

  18. [18]

    Substitutes, complements and ripples in network flows.Mathematics of Operations Research, 10(3):471–497, 1985

    Frieda Granot and Arthur F Veinott Jr. Substitutes, complements and ripples in network flows.Mathematics of Operations Research, 10(3):471–497, 1985

    1985

  19. [19]

    Princeton university press, 1998

    Donald M Topkis.Supermodularity and complementarity. Princeton university press, 1998. 31

    1998

  20. [20]

    Reliable facility location design under uncer- tain correlated disruptions.Manufacturing & Service Operations Management, 17(4):445–455, 2015

    Mengshi Lu, Lun Ran, and Zuo-Jun Max Shen. Reliable facility location design under uncer- tain correlated disruptions.Manufacturing & Service Operations Management, 17(4):445–455, 2015

    2015

  21. [21]

    Supermodularity in two-stage distributionally robust optimization.Management Science, 70(3):1394–1409, 2024

    Daniel Zhuoyu Long, Jin Qi, and Aiqi Zhang. Supermodularity in two-stage distributionally robust optimization.Management Science, 70(3):1394–1409, 2024

    2024

  22. [22]

    Preservation of supermodularity in parametric op- timization: Necessary and sufficient conditions on constraint structures.Operations Research, 69(1):1–12, 2021

    Xin Chen, Daniel Zhuoyu Long, and Jin Qi. Preservation of supermodularity in parametric op- timization: Necessary and sufficient conditions on constraint structures.Operations Research, 69(1):1–12, 2021

    2021

  23. [23]

    Transportation networks for research

    Transportation Networks for Research Core Team. Transportation networks for research. https://github.com/bstabler/TransportationNetworks. Accessed: October 31, 2025

    2025

  24. [24]

    hanging” arcs connected to componentg. Only one incident node of each “hanging

    David Simchi-Levi, Xin Chen, Julien Bramel, et al. The logic of logistics.Theory, algorithms, and applications for logistics and supply chain management, 2005. 32 Appendix A Proofs A.1 Proof of Proposition 2 Proof.We rewrite (8) as ϕ(x) = min y∈Rna c⊤y s.t.Ax+By≤h, (39) with A=   δ′  ∈R m×nv , B=   −T −I I   ∈R m×na, h=   −d f   ∈R m, wherem=n...

    2005

  25. [25]

    under attack ˆx, the shortest path ˆPs does not contain arca j; 2) under attack ˜x, the shortest path ˜Ps contains arca j. We rewritex= [x j, x⊤ s , x⊤ p , x⊤ o ]⊤, wherex s andx p consist of the entries ofxcorresponding to arcs in (A ˜Ps\A ˆPs )\{aj}andA ˆPs \A ˜Ps, respectively;x o consists of the other entries ofx. Hence, in an SPN, we have ϕp(ˆxp)< ϕ ...