Skip to main content
SpringerLink
Log in

Polynomial-time identification of robust network flows under uncertain arc failures

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

We propose Linear Programming (LP)-based solution methods for network flow problems subject to multiple uncertain arc failures, which allow finding robust optimal solutions in polynomial time under certain conditions. We justify this fact by proving that for the considered class of problems under uncertainty with linear loss functions, the number of entities in the corresponding LP formulations is polynomial with respect to the number of arcs in the network. The proposed formulation is efficient for sparse networks, as well as for time-critical networked systems, where quick and robust decisions play a crucial role.

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

Access this article

Log in via an institution

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

  1. Ahuja R.K., Magnanti T.L., Orlin J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, USA (1993)

    Google Scholar 

  2. Aneja Y.P., Chandrasekaran R., Nair K.P.K.: Maximizing residual flow under an arc destrucion. Networks 38(4), 194–198 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  3. Bertsekas D.P.: Network Optimization—Continuous and Discrete Models. Athena Scientific, Belmont (1998)

    MATH  Google Scholar 

  4. Bertsimas D., Sim M.: Robust discrete optimization and network flows. Math. Program. 98, 49–71 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  5. Casella, G., Berger, R.L.: Statistical Inference, 2nd edn. Duxbury (2002)

  6. Commander C.W., Pardalos P.M., Ryabchenko V., Uryasev S.: The wireless network jamming problem. J. Comb. Optim. 14(4), 481–498 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  7. Corea G.A., Kulkarni V.G.: Minimum cost routing on stochastic networks. Oper. Res. 38(3), 527–536 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  8. Cormican K.J., Morton D.P., Wood R.K.: Stochastic network interdiction. Oper. Res. 46(2), 184–197 (1998)

    Article  MATH  Google Scholar 

  9. Dantzig G.B.: Linear Programming and Extensions. Princeton University Press, New Jersey (1963)

    MATH  Google Scholar 

  10. Doulliez P.J., Rao M.R.: Maximal flow in a multi-terminal network with any one arc subject to failure. Manag. Sci. 18(1), 48–58 (1971)

    Article  MATH  Google Scholar 

  11. Garey M.R., Johnson D.S.: Computers and Intractability. A Guide to the Theory of NP-completeness. W.H. Freeman and Company, New York (1979)

    MATH  Google Scholar 

  12. Glockner G.D., Nemhauser G.L.: A dynamic network flow problem with uncertain arc capacities: formulation and problem structure. Oper. Res. 48(2), 233–242 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  13. Holton G.: Value-at-Risk: Theory and Practice. Academic Press, Dublin (2003)

    Google Scholar 

  14. Krokhmal P., Palmquist J., Uryasev S.: Portfolio optimization with conditional value-at-risk objective and constraints. J. Risk 4(2), 11–27 (2002)

    Google Scholar 

  15. Rockafellar R.T.: Network Flows and Monotropic Programming. Wiley, New York (1984)

    Google Scholar 

  16. Rockafellar R.T., Uryasev S.: Optimization of conditional value-at-risk. J. Risk 2(3), 21–41 (2000)

    Google Scholar 

  17. Rockafellar R.T., Uryasev S.: Conditional value-at-risk for general loss distributions. J. Banking Finance 26, 1443–1471 (2002)

    Article  Google Scholar 

  18. Schrijver A.: On the history of the transportation and maximum flow problem. Math. Program. 91, 437–445 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  19. Xpress-MP Solver. Dash Optimization, Inc

  20. Uryasev S.: Conditional value-at-risk: optimization algorithms and applications. Financial Eng. News 14, 1–5 (2000)

    MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Industrial and Systems Engineering, Research and Engineering Education Facility (REEF), University of Florida, Shalimar, FL, USA

    Vladimir L. Boginski

  2. Air Force Research Laboratory, Munitions Directorate, Eglin Air Force Base, Niceville, FL, USA

    Clayton W. Commander

  3. Risk Management and Financial Engineering Lab, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL, USA

    Timofey Turko

Authors
  1. Vladimir L. Boginski
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Clayton W. Commander
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Timofey Turko
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Vladimir L. Boginski.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Boginski, V.L., Commander, C.W. & Turko, T. Polynomial-time identification of robust network flows under uncertain arc failures. Optim Lett 3, 461–473 (2009). https://doi.org/10.1007/s11590-009-0125-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-009-0125-x

Keywords

Search

Navigation