Skip to main content
SpringerLink
Log in

Obtaining lower bounds from the progressive hedging algorithm for stochastic mixed-integer programs

  • Full Length Paper
  • Series B
  • Published:
Mathematical Programming Submit manuscript

Abstract

We present a method for computing lower bounds in the progressive hedging algorithm (PHA) for two-stage and multi-stage stochastic mixed-integer programs. Computing lower bounds in the PHA allows one to assess the quality of the solutions generated by the algorithm contemporaneously. The lower bounds can be computed in any iteration of the algorithm by using dual prices that are calculated during execution of the standard PHA. We report computational results on stochastic unit commitment and stochastic server location problem instances, and explore the relationship between key PHA parameters and the quality of the resulting lower bounds.

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

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

References

  1. Ahmed, S., Tawarmalani, M., Sahinidis, N.V.: A finite branch and bound algorithm for two-stage stochastic integer programs. Math. Program. Ser. A 100(2), 355–377 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  2. Boyd, S., Parihk, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found Trends Mach Learn 3, 1–22 (2011)

  3. Carøe, C.C., Schultz, R.: Dual decomposition in stochastic integer programming. Oper. Res. Lett. 24(1), 37–45 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  4. Carrión, M., Arroyo, J.M.: A computationally efficient mixed-integer linear formulation for the thermal unit commitment problem. IEEE Trans. Power Syst. 21(3), 1371–1378 (2006)

    Article  Google Scholar 

  5. Cheung, K., Gade, D., Monroy, C.S., Ryan, S.M., Watson, J.P., Wets, R.J.B., Woodruff, D.L.: Scalable stochastic unit commitment, part 2: solver performance. Energy Syst. 6, 309–329 (2015)

    Article  Google Scholar 

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

    Article  MATH  Google Scholar 

  7. Crainic, T., Hewitt, M., Rei, W.: Scenario grouping in a progressive hedging-based meta-heuristics for stochastic network design. Comput. Oper. Res. 43, 90–99 (2014)

    Article  MathSciNet  Google Scholar 

  8. Dantzig, G.B., Wolfe, P.: Decomposition principle for linear programs. Oper. Res. 8(1), 101–111 (1960)

    Article  MATH  Google Scholar 

  9. Eichhorn, A., Heitsch, H., Römisch, W.: Stochastic optimization of electricity portfolios: Scenario tree modeling and risk management. In: Rebennack, S., Pardalos, P.M., Pereira, M.V.F., Iliadis, N.A. (eds.) Handbook of Power Systems II, Energy Systems, pp. 405–432. Springer, Berlin (2010). doi:10.1007/978-3-642-12686-4_15

    Chapter  Google Scholar 

  10. Ela, E., Milligan, M., O’Malley, M.: A flexible power system operations simulation model for assessing wind integration. In: 2011 IEEE Power and Energy Society General Meeting. IEEE, New York (2011)

  11. Escudero, L., Garn, A., Prez, G., Unzueta, A.: Scenario cluster decomposition of the lagrangian dual in stochastic mixed 0–1 optimization. Comput. Oper. Res. 40, 362–377 (2013)

    Article  MathSciNet  Google Scholar 

  12. Guignard, M., Kim, S.: Lagrangean decomposition: a model yielding stronger lagrangean bounds. Math. Program. 39(2), 215–228 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  13. Guo, G., Hackebeil, G., Ryan, S., Watson, J., Woodruff, D.: Integration of progressive hedging and dual decomposition in stochastic integer programs. Oper. Res. Lett. 43, 311–316 (2015)

    Article  MathSciNet  Google Scholar 

  14. Hart, W., Watson, J., Woodruff, D.: Pyomo: Modeling and solving mathematical programs in Python. Math. Program. Comput. 3(3), 219–260 (2011)

  15. Held, H., Hemmecke, R., Woodruff, D.L.: A decomposition algorithm applied to planning the interdiction of stochastic networks. Naval Res. Logist. (NRL) 52(4), 321–328 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  16. Hiriart-Urruty, J.B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms. Springer, Berlin (1993)

    MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  18. Kaut, M., Wallace, S.: Evaluation of scenario-generation methods for stochastic programming. Pac. J. Optim. 3(2), 257–271 (2007)

    MathSciNet  MATH  Google Scholar 

  19. Løkketangen, A., Woodruff, D.L.: Progressive hedging and tabu search applied to mixed integer (0, 1) multistage stochastic programming. J. Heuristics 2, 111–128 (1996)

    Article  MATH  Google Scholar 

  20. Lubin, M., Martin, K., Petra, C., Sandıkçı, B.: On parallelizing dual decomposition in stochastic integer programming. Oper. Res. Lett. 41(3), 252–258 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  21. Lulli, G., Sen, S.: A branch-and-price algorithm for multistage stochastic integer programming with application to stochastic batch-sizing problems. Manag. Sci. 50(6), 786–796 (2004)

    Article  MATH  Google Scholar 

  22. Märkert, A., Gollmer, R.: User’s Guide to ddsip-AC Package for the Dual Decomposition of Two-Stage Stochastic Programs with Mixed-Integer Recourse. Department of Mathematics, University of Duisburg-Essen, Duisburg (2008)

    Google Scholar 

  23. Meyer, R.R.: On the existence of optimal solutions to integer and mixed-integer programming problems. Math. Program. 7(1), 223–235 (1974)

    Article  MathSciNet  MATH  Google Scholar 

  24. Morales-Espana, G., Latorre, J.M., Ramos, A.: Tight and compact MILP formulation for the thermal unit commitment problem. IEEE Trans. Power Syst. 21, 4897–4908 (2013)

    Article  Google Scholar 

  25. Mulvey, J.M., Vladimirou, H.: Applying the progressive hedging algorithm to stochastic generalized networks. Ann. Oper. Res. 31, 399–424 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  26. Mulvey, J.M., Vladimirou, H.: Solving multistage stochastic networks: an appplication of scenario aggregation. Networks 21, 619–643 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  27. Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization, vol. 27. Wiley, New York (1988)

    MATH  Google Scholar 

  28. Ntaimo, L., Sen, S.: The million-variable march for stochastic combinatorial optimization. J. Glob. Optim. 32, 385–400 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  29. Papavasiliou, A., Oren, S.S.: Multiarea stochastic unit commitment for high wind penetration in a transmission constrained network. Oper. Res. 61(3), 578–592 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  30. Pflug, G.C., Pichler, A.: Approximations for probability distributions and stochastic optimization problems. In: Bertocchi, M., Consigli, G., Dempster, M.A. (eds.) Stochastic Optimization Methods in Finance and Energy, International Series in Operations Research and Management Science. Springer, Berlin (2011)

    Google Scholar 

  31. Rockafellar, R.T., Wets, R.J.B.: Scenarios and policy aggregation in optimization under uncertainty. Math. Oper. Res. 16(1), 119–147 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  32. Ruiz, P.A., Philbrick, R.C., Zack, E., Cheung, K.W., Sauer, P.W.: Uncertainty management in the unit commitment problem. IEEE Trans. Power Syst. 24(2), 642–651 (2009)

    Article  Google Scholar 

  33. Ryan, S.M., Wets, R.J.B., Woodruff, D.L., Silva-Monroy, C., Watson, J.P.: Toward scalable, parallel progressive hedging for stochastic unit commitment. In: 2013 IEEE Power and Energy Society General Meeting. IEEE, New York (2013)

  34. Santoso, T., Ahmed, S., Goetschalckx, M., Shapiro, A.: A stochastic programming approach for supply chain network design under uncertainty. Eur. J. Oper. Res. 167(1), 96–115 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  35. Shor, N.Z., Kiwiel, K.C., Ruszczynski, A.: Minimization Methods for Non-differentiable Functions, vol. 3. Springer, Berlin (1985)

    Google Scholar 

  36. Sun, J., Tesfatsion, L.: Dynamic testing of wholesale power market designs: an open-source agent-based framework. Comput. Econ. 30(3), 291–327 (2007)

    Article  MATH  Google Scholar 

  37. Takriti, S., Birge, J.R., Long, E.: A stochastic model for the unit commitment problem. IEEE Trans. Power Syst. 11(3), 1497–1508 (1996)

    Article  Google Scholar 

  38. van der Vlerk, M.H.: Stochastic integer programming bibliography. http://www.eco.rug.nl/mally/biblio/sip.html (1996–2007)

  39. Watson, J., Woodruff, D., Hart, W.: PySP: Modeling and solving stochastic programs in Python. Math. Program. Comput. 4(2), 109–149 (2012)

  40. Watson, J.P., Woodruff, D.L.: Progressive hedging innovations for a class of stochastic mixed-integer resource allocation problems. Comput. Manag. Sci. 8(4), 355–370 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  41. Wets, R.J.B.: On the relation between stochastic and deterministic optimization. In: Bensoussan, A., Lions, J.L. (eds.) Control Theory, Numerical Methods and Computer Systems Modelling, pp. 350–361. Springer, Berlin (1975)

  42. Wets, R.J.B.: The aggregation principle in scenario analysis and stochastic optimization. In: Wallace, S.W. (ed.) Algorithms and Model Formulations in Mathematical Programming, pp. 91–113. Springer, Berlin (1989)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Sabre Holdings, Southlake, TX, 76092, USA

    Dinakar Gade

  2. Sandia National Laboratories, Albuquerque, NM, 87185, USA

    Jean-Paul Watson

  3. Texas A&M University, College Station, TX, 77843, USA

    Gabriel Hackebeil

  4. Iowa State University, Ames, IA, 50011, USA

    Sarah M. Ryan

  5. University of California Davis, Davis, CA, 95616, USA

    Roger J.-B. Wets & David L. Woodruff

Authors
  1. Dinakar Gade
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Gabriel Hackebeil
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Sarah M. Ryan
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Jean-Paul Watson
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Roger J.-B. Wets
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. David L. Woodruff
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to David L. Woodruff.

Additional information

This research was sponsored in part by the US Department of Energy’s ARPA-e Green Energy Network Integration (GENI) program, and by the Department of Energy’s Office of Science, Advanced Scientific Computing Research program. Thanks to Ge Guo for assistance with the numerical results. Sandia is a multi-program laboratory operated by Sandia Corporation, a Lockheed Martin Company, for the United States Department of Energy’s National Nuclear Security Administration under Contract DE-AC04-94-AL85000.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Gade, D., Hackebeil, G., Ryan, S.M. et al. Obtaining lower bounds from the progressive hedging algorithm for stochastic mixed-integer programs. Math. Program. 157, 47–67 (2016). https://doi.org/10.1007/s10107-016-1000-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-016-1000-z

Keywords

Mathematics Subject Classification

Search

Navigation