zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
A two-stage stochastic programming model for transportation network protection. (English) Zbl 1179.90246
Summary: Network protection against natural and human-caused hazards has become a topical research theme in engineering and social sciences. This paper focuses on the problem of allocating limited retrofit resources over multiple highway bridges to improve the resilience and robustness of the entire transportation system in question. The main modeling challenges in network retrofit problems are to capture the interdependencies among individual transportation facilities and to cope with the extremely high uncertainty in the decision environment. In this paper, we model the network retrofit problem as a two-stage stochastic programming problem that optimizes a mean-risk objective of the system loss. This formulation hedges well against uncertainty, but also imposes computational challenges due to involvement of integer decision variables and increased dimension of the problem. An efficient algorithm is developed, via extending the well-known L-shaped method using generalized benders decomposition, to efficiently handle the binary integer variables in the first stage and the nonlinear recourse in the second stage of the model formulation. The proposed modeling and solution methods are general and can be applied to other network design problems as well.

90C15Stochastic programming
90B15Network models, stochastic (optimization)
Full Text: DOI
[1] Housner, GW, Thiel CC, editors. Continuing challenge: the Northridge earthquake of January 17, 1994: Report to the Director, California Department of Transportation, by the Seismic Advisory Board. Sacramento, CA: Caltrans; 1994.
[2] Okuyama Y, Chang SE, co-editors. Modeling spatial economic impacts of disasters. Berlin: Springer; 2004.
[3] Yashinsky, M.: Performance of Bridge seismic retrofits during northridge earthquake, Journal of Bridge engineering 3, No. 1, 1-14 (1998)
[4] Werner SD, Taylor CE, Moore JE, Walton JS. Seismic retrofitting manuals for highway systems, volume I, seismic risk analysis of highway systems, and technical report for volume I. Buffalo, New York: Multidisciplinary Center for Earthquake Engineering Research; 1999.
[5] Shinozuka M, Juran I, O’rouke T, co-editors. In: Proceedings of workshop on mitigation of earthquake disasters by advanced technology (MEDAT-1). MCEER Technical Report; 2000.
[6] Beavers JE, editor. Advancing mitigation technologies and disaster response for lifeline systems. Technical Council on Lifeline Earthquake Engineering, ASCE, 2003.
[7] Magnanti, T. L.; Wong, R. T.: Network design and transportation planning: models and algorithms, Transportation science 18, 1-55 (1984)
[8] Yang, H.; Bell, M. G. H.: Models and algorithms for road network design: a review and some new developments, Transport reviews 18, 257-278 (1998)
[9] Dantzig, G. B.: Linear programming under uncertainty, Management science 1, 197-206 (1955) · Zbl 0995.90589
[10] Wets, R. J. B.: Programming under uncertainty: the equivalent convex program, SIAM journal of applied mathematics 14, No. 1, 89-105 (1966) · Zbl 0139.13303 · doi:10.1137/0114008
[11] Van Slyke, R. M.; Wets, R. J. B.: L-shaped programs with applications to optimal control and stochastic linear programming, SIAM journal of applied mathematics 17, 638-663 (1969) · Zbl 0197.45602 · doi:10.1137/0117061
[12] Wets, R. J. B.: Stochastic programs with fixed recourse: the equivalent deterministic program, SIAM review 16, 309-339 (1974) · Zbl 0311.90056 · doi:10.1137/1016053
[13] Verweij, B.; Ahmed, S.; Kleywegt, A. L.; Nemhauser, G.; Shapiro, A.: The sample average approximation method applied to stochastic routing problems: a computational study, Computational and applied optimization 24, 289-333 (2003) · Zbl 1094.90029 · doi:10.1023/A:1021814225969
[14] Gendreau, M.; Laporte, G.; S’eguin, R.: Stochastic vehicle routing, European journal of operational research 88, 3-12 (1996) · Zbl 0913.90094 · doi:10.1016/0377-2217(95)00050-X
[15] Ahmed, S.; King, A. J.; Parija, G.: A multi-stage stochastic integer programming approach for capacity expansion under uncertainty, Journal of global optimization 26, 3-24 (2003) · Zbl 1116.90382 · doi:10.1023/A:1023062915106
[16] Geoffrion, A. M.: Generalized benders decomposition, Journal of optimization theory and applications 10, 237-260 (1972) · Zbl 0229.90024 · doi:10.1007/BF00934810
[17] Ahmed, S.: Convexity and decomposition of mean-risk stochastic programs, Mathematical programming 106, 433-446 (2006) · Zbl 1134.90025 · doi:10.1007/s10107-005-0638-8
[18] Jonsbraten, T.; Wets, R.; Woodruff, D.: A class of stochastic programs with decision dependent random elements, Annals of operations research 82, 83-106 (1998) · Zbl 0911.90268 · doi:10.1023/A:1018943626786
[19] Benders, J. F.: Partitioning procedures for solving mixed variables programming problems, Numerische Mathematik 4, 238-252 (1962) · Zbl 0109.38302 · doi:10.1007/BF01386316
[20] Jr., J. E. Kelley: The cutting-plane method for solving convex programs, Journal of SIAM 8, 703-712 (1960) · Zbl 0098.12104 · doi:10.1137/0108053
[21] Ouorou, A.; Mahey, P.; Vial, J. -Ph.: A survey of algorithms for convex multicommodity flow problems, Management science 46, No. 1, 126-147 (2000) · Zbl 1231.90110 · doi:10.1287/mnsc.
[22] Leblanc, L. J.: An algorithm for the discrete network design problem, Transportation science 9, 183-199 (1975)
[23] Birge, J. R.; Louveaux, F. V.: Introduction to stochastic programming, (1997) · Zbl 0892.90142
[24] Lin, GH, Fukushima M. A class of mathematical programs with complementarity constraints: reformulations and algorithms. Technical Report 2003-10, Department of Applied Mathematics and Physics, Kyoto University, Kyoto, Japan, 2003.
[25] Evgrafov, A.; Patriksson, M.: On the existence of solutions to stochastic mathematical programs with equilibrium constraints, Journal of optimization theory and applications 121, 65-76 (2004) · Zbl 1140.90472 · doi:10.1023/B:JOTA.0000026131.04418.b7
[26] Shapiro, A.: Stochastic programming with equilibrium constraints, Journal of optimization theory and applications 128, No. 1, 223-243 (2006) · Zbl 1130.90032 · doi:10.1007/s10957-005-7566-x
[27] Kouvelis, P.; Yu, G.: Robust discrete optimization and its applications, (1997) · Zbl 0873.90071