Top

Published in:

2021 | OriginalPaper | Chapter

6. Parametric Stochastic Programming with One Chance Constraint: Gaining Insights from Response Space Analysis

Authors : Harvey J. Greenberg, Jean-Paul Watson, David L. Woodruff

Published in: Harvey J. Greenberg

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We consider stochastic programs with discrete scenario probabilities where scenario-specific constraints must hold with some probability, which we vary parametrically. We thus obtain minimum cost as a function of constraint-satisfaction probability. We characterize this trade-off using Everett’s response space and introduce an efficient construction of the response space frontier based on tangential approximation, a method introduced for one specified right-hand side. Generated points in the response space are optimal for a finite set of probabilities, with Lagrangian bounds equal to the piece-wise linear functional value. We apply our procedures to a number of illustrative stochastic mixed-integer programming models, emphasizing insights obtained and tactics for gaining more information about the trade-off between solution cost and probability of scenario satisfaction. Our code is an extension of the PySP stochastic programming library, included with the Pyomo (Python Optimization Modeling Objects) open-source optimization library.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Development of Publications and Community at the Interface Between Operations Research and Computing

next chapter An Analysis of Multiple Contaminant Warning System Design Objectives for Sensor Placement Optimization in Water Distribution Networks

S. Ahmed, A. Shapiro, Chapter 12: solving chance-constrained stochastic programs via sampling and integer programming, in TutORials in Operations Research, ed. by Z.-L. Chen, S. Raghavan (INFORMS, Catonsville, 2008), pp. 261–269

R. Brooks, A. Geoffrion, Finding Everett’s Lagrange multipliers by linear programming. Oper. Res. 14(6), 1149–1153 (1966)CrossRef

A. Charnes, W.W. Cooper, Systems evaluation and repricing theorems. Manag. Sci. 9(1), 33–49 (1962)CrossRef

J.P. Evans, F.J. Gould, S.M. Howe, A note on extended GLM. Oper. Res. 19(4), 1079–1080 (1971)CrossRef

H. Everett, III, Generalized Lagrange multiplier method for solving problems of optimum allocation of resources. Oper. Res. 11(3), 399–417 (1963)CrossRef

A.M. Geoffrion, The purpose of mathematical programming is insight, not numbers. Interfaces 7(1), 81–92 (1976)CrossRef

F.J. Gould, Extensions of Lagrange multipliers in nonlinear programming. SIAM J. Appl. Math. 17(6), 1280–1297 (1969)CrossRef

H.J. Greenberg, Lagrangian duality gaps: Their source and resolution. Technical Report CP-69005, Southern Methodist University, Dallas (1969). http://math.ucdenver.edu/~hgreenbe/pubs.shtml

H.J. Greenberg, Bounding nonconvex programs by conjugates. Oper. Res. 21(1), 346–348 (1973)CrossRef

10.

H.J. Greenberg, The one dimensional generalized Lagrange multiplier problem. Oper. Res. 25(2), 338–345 (1977)CrossRef

11.

H.J. Greenberg, Supplement: tolerances, in [Holder, A. (ed.), Mathematical Programming Glossary. INFORMS Comput. Soc. (2014)]. Posted 2003. Also appears at Optimization Online. http://www.optimization-online.org/DB_HTML/2012/05/3486.html

12.

H.J. Greenberg, Supplement: myths and counterexamples in mathematical programming, in [A. Holder (ed.), Mathematical Programming Glossary. INFORMS Comput. Soc. (2014)]. Posted 2010

13.

H.J. Greenberg, Supplement: Lagrangian saddle point equivalence, in [A. Holder (ed.), Mathematical Programming Glossary. INFORMS Comput. Soc. (2014)]. Transcribed from 1969 Course Notes

14.

H.J. Greenberg, Supplement: response space, in [A. Holder (ed.), Mathematical Programming Glossary. INFORMS Comput. Soc. (2014)]. Transcribed from 1969 Course Notes

15.

H.J. Greenberg, T. Robbins, Finding Everett’s Lagrange multipliers by generalized linear programming. Technical Report CP-70008, Southern Methodist University, Dallas, 1970. http://math.ucdenver.edu/~hgreenbe/pubs.shtml

16.

W.E. Hart, J.P. Watson, D.L. Woodruff, Python optimization modeling objects (Pyomo). Math. Program. Comput. 3(3), 219–260 (2011)CrossRef

17.

W.E. Hart, C. Laird, J.-P. Watson, D.L. Woodruff, Pyomo—Optimization Modeling in Python (Springer, Berlin, 2012)CrossRef

18.

A. Holder (ed.), Mathematical Programming Glossary. INFORMS Comput. Soc. (2014). http://glossary.computing.society.informs.org

19.

S. Küçukyavuz, On mixing sets arising in chance-constrained programming. Math. Program. 132(1–2), 31–56 (2012). ISSN 0025-5610. https://doi.org/10.1007/s10107-010-0385-3 CrossRef

20.

M.A. Lejeune, S. Shen, Multi-objective probabilistically constrained programming with variable risk: new models and applications. Eur. J. Oper. Res. 252(2), 522–539 (2016)CrossRef

21.

J. Luedtke, An integer programming and decomposition approach to general chance-constrained mathematical programs, in Integer Programming and Combinatorial Optimization, ed. by F. Eisenbrand, F. Shepherd. Lecture Notes in Computer Science, vol. 6080 (Springer, Berlin, 2010), pp. 271–284. ISBN: 978-3-642-13035-9

22.

J. Luedtke, A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with finite support. Math. Program. A 146, 219–244 (2014)CrossRef

23.

J. Luedtke, S. Ahmed, G.L. Nemhauser, An integer programming approach for linear programs with probabilistic constraints. Math. Program. 122(2), 247–272 (2010). ISSN: 0025-5610. https://doi.org/10.1007/s10107-008-0247-4 CrossRef

24.

A. Nemirovski, A. Shapiro, Convex approximations of chance constrained programs. SIAM J. Optim. 17(4), 969–996 (2006)CrossRef

25.

A. Prekopa, Probabilistic programming, in Handbooks in Operations Research and Management Science, Volume 10: Stochastic Programming, ed. by A. Ruszczyński, A. Shapiro (Elsevier, Amsterdam, 2003)

26.

T. Rengarajan, D. P. Morton, Estimating the efficient frontier of a probabilistic bicriteria model, in Proceedings of the 2009 Winter Simulation Conference, ed. by M.D. Rossetti, R.R. Hill, B. Johansson, A. Dunkin, R.G. Ingalls (2009), pp. 494–504

27.

T. Rengarajan, N. Dimitrov, D.P. Morton, Convex approximations of a probabilistic bicriteria model with disruptions. INFORMS J. Comput. 25(1), 147–160 (2013)CrossRef

28.

A. Ruszczyński, Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra. Math. Program. 93(2), 195–215 (2002)CrossRef

29.

J.F. Shapiro, Generalized Lagrange multipliers in integer programming. Oper. Res. 19(1), 68–76 (1971)CrossRef

30.

S. Shen, Using integer programming for balancing return and risk in problems with individual chance constraints. Comput. Oper. Res. 49, 59–70 (2014)CrossRef

31.

J.-P. Watson, R.J.-B. Wets, D.L. Woodruff, Scalable heuristics for a class of chance-constrained stochastic programs. INFORMS J. Comput. 22(4), 543–554 (2010). ISSN: 1526-5528. https://doi.org/10.1287/ijoc.1090.0372 CrossRef

32.

J.-P. Watson, D.L. Woodruff, W.E. Hart, Modeling and solving stochastic programs in Python. Math. Program. Comput. 4(2), 109–149 (2012)CrossRef

33.

W.B. Widhelm, Geometric interpretation of generalized Lagrangian multiplier search procedures in the payoff space. Oper. Res. 28(3), 822–827 (1980)CrossRef

34.

P.L. Yu, M. Zeleny, Linear multiparametric programming by multicriteria simplex method. Manag. Sci. 23(2), 159–170 (1976)CrossRef

Title: Parametric Stochastic Programming with One Chance Constraint: Gaining Insights from Response Space Analysis
Authors: Harvey J. Greenberg
Jean-Paul Watson
David L. Woodruff
Publisher: Springer International Publishing
Book: Harvey J. Greenberg
Print ISBN: 978-3-030-56428-5

Electronic ISBN: 978-3-030-56429-2

Copyright Year: 2021
DOI: https://doi.org/10.1007/978-3-030-56429-2_6

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"