Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

New solution approaches for the maximum-reliability stochastic network interdiction problem

  • Original Paper
  • Published:
Computational Management Science Aims and scope Submit manuscript

Abstract

We investigate methods to solve the maximum-reliability stochastic network interdiction problem (SNIP). In this problem, a defender interdicts arcs on a directed graph to minimize an attacker’s probability of undetected traversal through the network. The attacker’s origin and destination are unknown to the defender and assumed to be random. SNIP can be formulated as a stochastic mixed-integer program via a deterministic equivalent formulation (DEF). As the size of this DEF makes it impractical for solving large instances, current approaches to solving SNIP rely on modifications of Benders decomposition. We present two new approaches to solve SNIP. First, we introduce a new DEF that is significantly more compact than the standard DEF. Second, we propose a new path-based formulation of SNIP. The number of constraints required to define this formulation grows exponentially with the size of the network, but the model can be solved via delayed constraint generation. We present valid inequalities for this path-based formulation which are dependent on the structure of the interdicted arc probabilities. We propose a branch-and-cut (BC) algorithm to solve this new SNIP formulation. Computational results demonstrate that directly solving the more compact SNIP formulation and this BC algorithm both provide an improvement over a state-of-the-art implementation of Benders decomposition for this problem.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Ahmed S, Atamtürk A (2011) Maximizing a class of submodular utility functions. Math Program 128(1–2):149–169

    Article  Google Scholar 

  • Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows: theory, algorithms, and applications. Prentice Hall, Upper Saddle River

    Google Scholar 

  • Al-Khayyal FA, Falk JE (1983) Jointly constrained biconvex programming. Math Oper Res 8(2):273–286

    Article  Google Scholar 

  • Bodur M, Dash S, Günlük O, Luedtke J (2016) Strengthened benders cuts for stochastic integer programs with continuous recourse. INFORMS J Comput 29(1):77–91

    Article  Google Scholar 

  • Brown G, Carlyle M, Salmerón J, Wood K (2006) Defending critical infrastructure. Interfaces 36(6):530–544

    Article  Google Scholar 

  • Brown GG, Carlyle WM, Harney RC, Skroch EM, Wood RK (2009) Interdicting a nuclear-weapons project. Oper Res 57(4):866–877

    Article  Google Scholar 

  • Cormican KJ, Morton DP, Wood RK (1998) Stochastic network interdiction. Oper Res 46(2):184–197

    Article  Google Scholar 

  • Dimitrov NB, Michalopoulos DP, Morton DP, Nehme MV, Pan F, Popova E, Schneider EA, Thoreson GG (2011) Network deployment of radiation detectors with physics-based detection probability calculations. Ann Oper Res 187(1):207–228

    Article  Google Scholar 

  • Fortet R (1960) Applications de l’algèbre de Boole en recherche opérationelle. Rev Fr d’Inform et de Rech Opér 4(14):17–25

    Google Scholar 

  • Fulkerson DR, Harding GC (1977) Maximizing the minimum source-sink path subject to a budget constraint. Math Program 13(1):116–118

    Article  Google Scholar 

  • Golden B (1978) A problem in network interdiction. Nav Res Logist Q 25(4):711–713

    Article  Google Scholar 

  • Hemmecke R, Schultz R, Woodruff DL (2003) Interdicting stochastic networks with binary interdiction effort. In: Woodruff DL (ed) Network interdiction and stochastic integer programming. Springer, Berlin, pp 69–84

    Chapter  Google Scholar 

  • Janjarassuk U, Linderoth J (2008) Reformulation and sampling to solve a stochastic network interdiction problem. Networks 52(3):120–132

    Article  Google Scholar 

  • Lubin M, Dunning I (2015) Computing in operations research using Julia. INFORMS J Comput 27(2):238–248

    Article  Google Scholar 

  • McCormick GP (1976) Computability of global solutions to factorable nonconvex programs: part I—convex underestimating problems. Math Program 10(1):147–175

    Article  Google Scholar 

  • Morton DP (2011) Stochastic network interdiction. In: Cochran JJ (ed) Wiley encyclopedia of operations research and management science. Wiley, Hoboken

    Google Scholar 

  • Morton DP, Pan F, Saeger KJ (2007) Models for nuclear smuggling interdiction. IIE Trans 39(1):3–14

    Article  Google Scholar 

  • Nemhauser GL, Wolsey LA (1988) Integer and combinatorial optimization. Wiley, New York

    Google Scholar 

  • Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions—I. Math Program 14(1):265–294

    Article  Google Scholar 

  • Pan F, Morton DP (2008) Minimizing a stochastic maximum-reliability path. Networks 52(3):111–119

    Article  Google Scholar 

  • Pan F, Charlton WS, Morton DP (2003) A stochastic program for interdicting smuggled nuclear material. In: Woodruff DL (ed) Network interdiction and stochastic integer programming. Springer, Berlin, pp 1–19

    Google Scholar 

  • Schrivjer A (2003) Combinatorial optimization: polyhedra and efficiency. Springer, Berlin

    Google Scholar 

  • Wollmer R (1964) Removing arcs from a network. Oper Res 12(6):934–940

    Article  Google Scholar 

  • Wood RK (1993) Deterministic network interdiction. Math Comput Model 17(2):1–18

    Article  Google Scholar 

  • Yu J, Ahmed S (2017) Maximizing a class of submodular utility functions with constraints. Math Program 162(1–2):145–164

    Article  Google Scholar 

Download references

Acknowledgements

This work was supported by National Science Foundation Grants CMMI-1130266 and SES-1422768.

Author information

Authors and Affiliations

  1. Department of Industrial and Systems Engineering, University of Wisconsin–Madison, Madison, WI, 53706, USA

    Eli Towle & James Luedtke

Authors
  1. Eli Towle
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. James Luedtke
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Eli Towle.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Towle, E., Luedtke, J. New solution approaches for the maximum-reliability stochastic network interdiction problem. Comput Manag Sci 15, 455–477 (2018). https://doi.org/10.1007/s10287-018-0321-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10287-018-0321-1

Keywords

Search

Navigation