[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Stochastic dual dynamic integer programming

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

Abstract

Multistage stochastic integer programming (MSIP) combines the difficulty of uncertainty, dynamics, and non-convexity, and constitutes a class of extremely challenging problems. A common formulation for these problems is a dynamic programming formulation involving nested cost-to-go functions. In the linear setting, the cost-to-go functions are convex polyhedral, and decomposition algorithms, such as nested Benders’ decomposition and its stochastic variant, stochastic dual dynamic programming (SDDP), which proceed by iteratively approximating these functions by cuts or linear inequalities, have been established as effective approaches. However, it is difficult to directly adapt these algorithms to MSIP due to the nonconvexity of integer programming value functions. In this paper we propose an extension to SDDP—called stochastic dual dynamic integer programming (SDDiP)—for solving MSIP problems with binary state variables. The crucial component of the algorithm is a new reformulation of the subproblems in each stage and a new class of cuts, termed Lagrangian cuts, derived from a Lagrangian relaxation of a specific reformulation of the subproblems in each stage, where local copies of state variables are introduced. We show that the Lagrangian cuts satisfy a tightness condition and provide a rigorous proof of the finite convergence of SDDiP with probability one. We show that, under fairly reasonable assumptions, an MSIP problem with general state variables can be approximated by one with binary state variables to desired precision with only a modest increase in problem size. Thus our proposed SDDiP approach is applicable to very general classes of MSIP problems. Extensive computational experiments on three classes of real-world problems, namely electric generation expansion, financial portfolio management, and network revenue management, show that the proposed methodology is very effective in solving large-scale multistage stochastic integer optimization problems.

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
£29.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 includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. Abgottspon, H., Njalsson, K., Bucher, M., Andersson, G., et al.: Risk-averse medium-term hydro optimization considering provision of spinning reserves. In: 2014 International Conference on Probabilistic Methods Applied to Power Systems (PMAPS), pp. 1–6. IEEE (2014)

  2. Ahmed, S.: Two-stage stochastic integer programming: a brief introduction. In: Cochran et al. (eds.) Wiley Encyclopedia of Operations Research and Management Science (2010)

  3. Ahmed, S., Sahinidis, N.V.: An approximation scheme for stochastic integer programs arising in capacity expansion. Oper. Res. 51(3), 461–471 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  4. Ahmed, S., King, A.J., Parija, G.: A multi-stage stochastic integer programming approach for capacity expansion under uncertainty. J. Glob. Optim. 26(1), 3–24 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  5. Akbari, T., Rahimikian, A., Kazemi, A.: A multi-stage stochastic transmission expansion planning method. Energy Convers. Manag. 52(8), 2844–2853 (2011)

    Article  Google Scholar 

  6. Alonso-Ayuso, A., Escudero, L.F., Ortuno, M.T.: BFC, a branch-and-fix coordination algorithmic framework for solving some types of stochastic pure and mixed 0–1 programs. Eur. J. Oper. Res. 151(3), 503–519 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  7. Angulo, G., Ahmed, S., Dey, S.S.: Improving the integer L-shaped method. INFORMS J. Comput. 28, 483–499 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  8. Baringo, L., Conejo, A.J.: Risk-constrained multi-stage wind power investment. IEEE Trans. Power Syst. 28(1), 401–411 (2013)

    Article  Google Scholar 

  9. Barnhart, C., Johnson, E.L., Nemhauser, G.L., Savelsbergh, M.W., Vance, P.H.: Branch-and-price: column generation for solving huge integer programs. Oper. Res. 46(3), 316–329 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  10. Barth, R., Brand, H., Meibom, P., Weber, C.: A stochastic unit-commitment model for the evaluation of the impacts of integration of large amounts of intermittent wind power. In: International Conference on Probabilistic Methods Applied to Power Systems, 2006. PMAPS 2006, pp. 1–8. IEEE (2006)

  11. Benders, J.F.: Partitioning procedures for solving mixed-variables programming problems. Numer. Math. 4(1), 238–252 (1962)

    Article  MathSciNet  MATH  Google Scholar 

  12. Bertsekas, D.P.: Nonlinear Programming. Athena Scientific, Belmont (1999)

    MATH  Google Scholar 

  13. Bienstock, D., Munoz, G.: LP approximations to mixed-integer polynomial optimization problems. arXiv:1501.00288 (2016)

  14. Birge, J.R.: Decomposition and partitioning methods for multistage stochastic linear programs. Oper. Res. 33(5), 989–1007 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  15. Boland, N., Dumitrescu, I., Froyland, G., Kalinowski, T.: Minimum cardinality non-anticipativity constraints sets for multistage stochastic programming. Math. Program. 157(2), 69–93 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  16. Bradley, S.P., Crane, D.B.: A dynamic model for bond portfolio management. Manage. Sci. 19(2), 139–151 (1972)

    Article  Google Scholar 

  17. Bruno, S., Ahmed, S., Shapiro, A., Street, A.: Risk neutral and risk averse approaches to multistage renewable investment planning under uncertainty. Eur. J. Oper. Res. 250(3), 979–989 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  18. Carino, D.R., Kent, T., Myers, D.H., Stacy, C., Sylvanus, M., Turner, A.L., Watanabe, K., Ziemba, W.T.: The Russell-Yasuda Kasai model: an asset/liability model for a Japanese insurance company using multistage stochastic programming. Interfaces 24(1), 29–49 (1994)

    Article  MATH  Google Scholar 

  19. 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 

  20. Cerisola, S., Baíllo, Á., Fernández-López, J.M., Ramos, A., Gollmer, R.: Stochastic power generation unit commitment in electricity markets: a novel formulation and a comparison of solution methods. Oper. Res. 57(1), 32–46 (2009)

    Article  MATH  Google Scholar 

  21. Cerisola, S., Latorre, J.M., Ramos, A.: Stochastic dual dynamic programming applied to nonconvex hydrothermal models. Eur. J. Oper. Res. 218(3), 687–697 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  22. Chen, L., Mello, T Homem-de: Re-solving stochastic programming models for airline revenue management. Ann. Oper. Res. 177(1), 91–114 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  23. Chen, Z.-L., Powell, W.B.: Convergent cutting-plane and partial-sampling algorithm for multistage stochastic linear programs with recourse. J. Optim. Theory Appl. 102(3), 497–524 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  24. Chen, Z.-L., Li, S., Tirupati, D.: A scenario-based stochastic programming approach for technology and capacity planning. Comput. Oper. Res. 29(7), 781–806 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  25. Dantzig, G.B., Infanger, G.: Multi-stage stochastic linear programs for portfolio optimization. Ann. Oper. Res. 45(1), 59–76 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  26. de Boer, S.V., Freling, R., Piersma, N.: Mathematical programming for network revenue management revisited. Eur. J. Oper. Res. 137(1), 72–92 (2002)

    Article  MATH  Google Scholar 

  27. Escudero, L.F., Kamesam, P.V., King, A.J., Wets, R.J.: Production planning via scenario modelling. Ann. Oper. Res. 43(6), 309–335 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  28. Escudero, L.F., Garin, A., Unzeuta, A.: Cluster lagrangean decomposition in multistage stochastic optimization. Comput. Oper. Res. 67, 48–62 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  29. Flach, B., Barroso, L., Pereira, M.: Long-term optimal allocation of hydro generation for a price-maker company in a competitive market: latest developments and a stochastic dual dynamic programming approach. IET Gener. Transm. Distrib. 4(2), 299–314 (2010)

    Article  Google Scholar 

  30. Fleten, S.-E., Kristoffersen, T.K.: Short-term hydropower production planning by stochastic programming. Comput. Oper. Res. 35(8), 2656–2671 (2008)

    Article  MATH  Google Scholar 

  31. Gade, D., Hackebeil, G., Ryan, S., Watson, J.-P., Wets, R., Woodruff, D.L.: Obtaining lower bounds from the progressive hedging algorithm for stochastic mixed-integer programs. Math. Program. 157(1), 47–67 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  32. Geoffrion, A.M.: Lagrangian relaxation for integer programming. Math. Program. Study 2, 82–114 (1974)

    Article  MathSciNet  MATH  Google Scholar 

  33. Girardeau, P., Leclere, V., Philpott, A.: On the convergence of decomposition methods for multistage stochastic convex programs. Math. Oper. Res. 40(1), 130–145 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  34. Gjelsvik, A., Belsnes, M.M., Haugstad, A.: An algorithm for stochastic medium-term hydrothermal scheduling under spot price uncertainty. In: Proceedings of 13th Power Systems Computation Conference (1999)

  35. Glover, F.: Improved linear integer programming formulations of nonlinear integer problems. Manage. Sci. 22(4), 455–460 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  36. Golub, B., Holmer, M., McKendall, R., Pohlman, L., Zenios, S.A.: A stochastic programming model for money management. Eur. J. Oper. Res. 85(2), 282–296 (1995)

    Article  MATH  Google Scholar 

  37. Gupta, V., Grossmann, I.E.: Multistage stochastic programming approach for offshore oilfield infrastructure planning under production sharing agreements and endogenous uncertainties. J. Petrol. Sci. Eng. 124, 180–197 (2014)

    Article  Google Scholar 

  38. Gupte, A., Ahmed, S., Cheon, M., Dey, S.: Solving mixed integer bilinear problems using MILP formulations. SIAM J. Optim. 23(721–744), 2013 (2013)

    MathSciNet  MATH  Google Scholar 

  39. Gupte, A., Ahmed, S., Cheon, M., Dey, S.: Relaxations and discretizations for the pooling problem. J. Glob. Optim. 67, 631–669 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  40. Heitsch, H., Römisch, W., Strugarek, C.: Stability of multistage stochastic programs. SIAM J. Optim. 17(2), 511–525 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  41. Helseth, A., Mo, B., Fodstad, M., Hjelmeland, M.N.: Co-optimizing sales of energy and capacity in a hydropower scheduling model. In: PowerTech, 2015 IEEE Eindhoven, pages 1–6. IEEE, (2015)

  42. Hiriart-Urruty, J.-B., Lemaréchal, C.: Convex analysis and minimization algorithms I: Fundamentals, volume 305. Springer Science & Business Media, (2013)

  43. Hoffman, A.J.: On approximate solutions of systems of linear inequalities. Journal of Research of the National Bureau of Standards 49(4), 263–265 (1952)

    Article  MathSciNet  Google Scholar 

  44. Høyland, K., Wallace, S.W.: Generating scenario trees for multistage decision problems. Manage. Sci. 47(2), 295–307 (2001)

    Article  MATH  Google Scholar 

  45. Infanger, G., Morton, D.: Cut sharing for multistage stochastic linear programs with interstage dependency. Math. Program. 75(2), 241–256 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  46. Jacobs, J., Freeman, G., Grygier, J., Morton, D., Schultz, G., Staschus, K., Stedinger, J.: Socrates: A system for scheduling hydroelectric generation under uncertainty. Ann. Oper. Res. 59(1), 99–133 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  47. Jin, S., Ryan, S.M., Watson, J.-P., Woodruff, D.L.: Modeling and solving a large-scale generation expansion planning problem under uncertainty. Energy Systems 2(3–4), 209–242 (2011)

    Article  Google Scholar 

  48. Kuhn, D.: Generalized bounds for convex multistage stochastic programs, volume 548. Springer Science & Business Media, (2006)

  49. Kusy, M.I., Ziemba, W.T.: A bank asset and liability management model. Oper. Res. 34(3), 356–376 (1986)

    Article  Google Scholar 

  50. Laporte, G., Louveaux, F.V.: The integer l-shaped method for stochastic integer programs with complete recourse. Operations research letters 13(3), 133–142 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  51. Li, Y., Huang, G., Nie, S., Liu, L.: Inexact multistage stochastic integer programming for water resources management under uncertainty. J. Environ. Manage. 88(1), 93–107 (2008)

    Article  Google Scholar 

  52. Lohmann, T., Hering, A.S., Rebennack, S.: Spatio-temporal hydro forecasting of multireservoir inflows for hydro-thermal scheduling. Eur. J. Oper. Res. 255, 243–258 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  53. Löhndorf, N., Wozabal, D., Minner, S.: Optimizing trading decisions for hydro storage systems using approximate dual dynamic programming. Oper. Res. 61(4), 810–823 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  54. Lu, Y., Zhao, C., Watson, J.-P., Pan, K., Guan, Y.: Two-stage and multi-stage stochastic unit commitment under wind generation uncertainty. In: Proceedings of the IEEE PES Annual Conference (2014)

  55. Meibom, P., Barth, R., Hasche, B., Brand, H., Weber, C., O’Malley, M.: Stochastic optimization model to study the operational impacts of high wind penetrations in Ireland. IEEE Trans. Power Syst. 26(3), 1367–1379 (2011)

    Article  Google Scholar 

  56. Mokrian, P., Stephen, M.: A stochastic programming framework for the valuation of electricity storage. In: 26th USAEE/IAEE North American Conference, pp. 24–27 (2006)

  57. Möller, A., Römisch, W., Weber, K.: Airline network revenue management by multistage stochastic programming. Comput. Manage. Sci. 5, 355–377 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  58. Mulvey, J.M., Vladimirou, H.: Stochastic network programming for financial planning problems. Manage. Sci. 38(11), 1642–1664 (1992)

    Article  MATH  Google Scholar 

  59. Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, Hoboken (2014)

    MATH  Google Scholar 

  60. Newham, N., Wood, A.: Transmission investment planning using SDDP. In: Power Engineering Conference, 2007. AUPEC 2007. Australasian Universities, pp. 1–5. IEEE (2007)

  61. Nowak, M.P., Römisch, W.: Stochastic Lagrangian relaxation applied to power scheduling in a hydro-thermal system under uncertainty. Ann. Oper. Res. 100(1–4), 251–272 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  62. Owen, J., Mehrotra, S.: On the value of binary expansions for general mixed-integer linear programs. Oper. Res. 50, 810–819 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  63. Pappala, V.S., Erlich, I., Rohrig, K., Dobschinski, J.: A stochastic model for the optimal operation of a wind-thermal power system. IEEE Trans. Power Syst. 24(2), 940–950 (2009)

    Article  Google Scholar 

  64. Pennanen, T.: Epi-convergent discretizations of multistage stochastic programs via integration quadratures. Math. Program. 116(1–2), 461–479 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  65. Pereira, M.V., Pinto, L.M.: Stochastic optimization of a multireservoir hydroelectric system: a decomposition approach. Water Resour. Res. 21, 779–792 (1985)

    Article  Google Scholar 

  66. Pereira, M.V., Pinto, L.M.: Multi-stage stochastic optimization applied to energy planning. Math. Program. 52(1–3), 359–375 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  67. Pflug, G.C.: Scenario tree generation for multiperiod financial optimization by optimal discretization. Math. Program. 89(2), 251–271 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  68. Philpott, A., Wahid, F., Frédéric, B.: MIDAS: a mixed integer dynamic approximation scheme. Optimization-online (2016)

  69. Philpott, A.B., de Matos, V.L.: Dynamic sampling algorithms for multi-stage stochastic programs with risk aversion. Eur. J. Oper. Res. 218(2), 470–483 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  70. Philpott, A.B., Guan, Z.: On the convergence of stochastic dual dynamic programming and related methods. Oper. Res. Lett. 36(4), 450–455 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  71. Queiroz, A., Morton, D.: Sharing cuts under aggregated forecast when decomposing multi-stage stochastic programs. Oper. Res. Lett. 41, 311–316 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  72. Rebennack, S.: Combining sampling-based and scenario-based nested benders decomposition methods: application to stochastic dual dynamic programming. Math. Program. 156, 1–47 (2013)

    MathSciNet  Google Scholar 

  73. Rockafellar, R.T., Wets, R.: Scenario and policy aggregation in optimization under uncertainty. Math. Oper. Res. 16, 119–147 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  74. Römisch, W., Schultz, R.: Multistage stochastic integer programs: an introduction. In: Grötschel, M., Krumke, S.O., Rambau, J. (eds.) Online Optimization of Large Scale Systems, pp. 581–600. Springer, Berlin (2001)

    Chapter  Google Scholar 

  75. Ruszczynski, A., Shapiro, A.: Stochastic Programming, vol. 10. Elsevier, Amsterdam (2003)

    MATH  Google Scholar 

  76. Sandikci, B., Ozaltin, O.Y.: A scalable bounding method for multistage stochastic integer programs. Working paper 14-21, Booth School of Business, University of Chicago (2014)

  77. Sen, S., Yu, L., Genc, T.: A stochastic programming approach to power portfolio optimization. Oper. Res. 54(1), 55–72 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  78. Shapiro, A.: Inference of statistical bounds for multistage stochastic programming problems. Math. Methods Oper. Res. 58(1), 57–68 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  79. Shapiro, A.: On a time consistency concept in risk averse multistage stochastic programming. Oper. Res. Lett. 37(3), 143–147 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  80. Shapiro, A.: Analysis of stochastic dual dynamic programming method. Eur. J. Oper. Res. 209(1), 63–72 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  81. Shapiro, A.: Minimax and risk averse multistage stochastic programming. Eur. J. Oper. Res. 219(3), 719–726 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  82. Shapiro, A., Tekaya, W., da Costa, J.P., Soares, M.P.: Risk neutral and risk averse stochastic dual dynamic programming method. Eur. J. Oper. Res. 224(2), 375–391 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  83. Singh, K.J., Philpott, A.B., Wood, R.K.: Dantzig-wolfe decomposition for solving multistage stochastic capacity-planning problems. Oper. Res. 57(5), 1271–1286 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  84. Steeger, G., Rebennack, S.: Dynamic convexification within nested Benders decomposition using Lagrangian relaxation. Eur. J. Oper. Res. 357, 669–686 (2017)

    Article  MATH  Google Scholar 

  85. Takriti, S., Birge, J.R.: Lagrangian solution techniques and bounds for loosely coupled mixed-integer stochastic programs. Oper. Res. 48(1), 91–98 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  86. 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 

  87. Takriti, S., Krasenbrink, B., Wu, L.S.-Y.: Incorporating fuel constraints and electricity spot prices into the stochastic unit commitment problem. Oper. Res. 48(2), 268–280 (2000)

    Article  Google Scholar 

  88. Tawarmalani, M., Sahinidis, N.: Convex extensions and envelopes of lower semi-continuous functions. Math. Program. 93, 247–263 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  89. Thomé, F., Pereira, M., Granville, S., Fampa, M.: Non-convexities representation on hydrothermal operation planning using SDDP. www.psr-inc.com (2013) (submitted)

  90. Watkins, D.W., McKinney, D.C., Lasdon, L.S., Nielsen, S.S., Martin, Q.W.: A scenario-based stochastic programming model for water supplies from the highland lakes. Int. Trans. Oper. Res. 7(3), 211–230 (2000)

    Article  Google Scholar 

  91. Zenarosa, G.L., Prokopyev, O.A., Schaefer, A.J.: Scenario-tree decomposition: bounds for multistage stochastic mixed-integer programs. Working paper, Department of Industrial Engineering, University of Pittsburgh (2014)

Download references

Acknowledgements

The research in this paper is partially supported by the Grants from the National Science Foundation, NSF-1633196 and NSF-1331426.

Author information

Authors and Affiliations

  1. H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, 30332, USA

    Jikai Zou, Shabbir Ahmed & Xu Andy Sun

Authors
  1. Jikai Zou
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Shabbir Ahmed
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Xu Andy Sun
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Xu Andy Sun.

Appendix

Appendix

Definition 3

A convex underestimator of \(f: X\rightarrow \mathbb {R}\) is a convex function defined on \(\text {conv}(X)\) that is majorized by f on X. The largest convex underestimator of f on \(\text {conv}(X)\) is called the convex lower envelope of f.

Proof of Theorem 1

The graph of f, denoted as \(F :=\{(x,y)\in \{0,1\}^n\times \mathbb {R} : y = f(x)\}\), is a finite set. Define \(\Pi := \{(\alpha ,\beta ) \in \mathbb {R}^{n+1} : y \ge \alpha ^\top x + \beta , \; \forall (x,y)\in F\}\). Since F is a finite set, \(\Pi \) is a nonempty polyhedron. Define a function \(g(x):=\max _{(\alpha ,\beta )\in \Pi } \{\alpha ^\top x + \beta \}\) on \(C_n :=[0,1]^n\). First, we show that g(x) is a well-defined convex piecewise linear function with finite value, i.e. \(g(x)<\infty \) for all \(x\in C_n\) and \(g(x) = f(x)\) for all binary point \(x\in \{0,1\}^n\). Therefore, g is a convex underestimator of f on \(C_n\). Then we show that g(x) is the tightest convex underestimator, i.e. the convex lower envelope of f.

Consider the following linear program

$$\begin{aligned} (P)\quad \max _{\alpha ,\beta }\quad&{x}^\top \alpha + \beta \\ \text {s.t.}\quad&(\hat{x}^i)^\top \alpha + \beta \le \hat{y}^i,\quad \forall \hat{x}^i\in \{0,1\}^n, \; \hat{y}^i = f(\hat{x}^i), \end{aligned}$$

where \({x}\in C_n\), and its dual

$$\begin{aligned} (D)\quad \min \quad&\sum _{i=1}^N y^i \lambda ^i \\ \text {s.t.}\quad&\hat{X}\lambda = x \\&e^\top \lambda = 1 \\&\lambda \ge 0, \end{aligned}$$

where \(\hat{X} = [\hat{x}^1, \ldots ,\hat{x}^N]\) contains all the binary vectors in \(\{0,1\}^n\) as its columns and \(N=2^n\). Since \(C_n\) is the convex hull of \(\{0,1\}^n\), the dual problem (D) is always feasible and bounded for any \(x\in C_n\), which implies \(g(x)<\infty \) for all \(x\in C_n\). If \(x \in \{0,1\}^n\), i.e. \(x=\hat{x}^i\) for some \(i=1, \ldots ,N\), then the feasible region of the dual problem has a unique solution \(\lambda = e_i\), namely only the ith entry of \(\lambda \) is 1 and all other entries of \(\lambda \) are 0. Therefore, \(g(x)=f(x)\) for all \(x\in \{0,1\}^n\). Since \(\Pi \) is a polyhedron, g(x) is a convex piecewise linear function with a finite number of linear pieces, corresponding to extreme points of \(\Pi \).

Since any convex underestimator h of f on the open box \((0,1)^n\) can be expressed as a pointwise maximum of affine functions \(l(x) = \alpha ^\top x + \beta \), where the halfspace \(y\ge \alpha ^\top x + \beta \) contains F, then \(h(x) = \max _{(\alpha ,\beta )\in S} \{\alpha ^\top x + \beta \}\) for some subset \(S\subseteq \Pi \). Therefore, \(g(x)\ge h(x)\) for all \(x\in (0,1)^n\). On the boundary points \(x\in \{0,1\}^n\), since we already have \(g(x) = f(x)\ge h(x)\), thus, \(g(x)\ge h(x)\) for all \(x\in C_n\). Therefore, g(x) is the convex lower envelope of f. This completes the proof. \(\square \)

Remark

A key step in the proof of Theorem 1 uses the simple fact that if \(x\in \{0,1\}^n\) and x is the convex combination of a set of binary vectors, then x coincides with one of these binary vectors. This simple fact underlies a similar argument used to prove the key strong duality result in Sect. 4.3 Theorem 3.

Proof of Theorem 4

Consider an MSIP with \(d := d_1 + d_2\) mixed-integer state variables per node:

$$\begin{aligned} \begin{array}{rll} \displaystyle {\min _{x_n, y_n} } &{} \displaystyle {\sum _{n \in \mathcal {T}} }p_n f_n(x_n,y_n) &{} \\ \mathrm{s.t.} &{} (x_{a(n)}, x_n, y_n) \in X_n &{} \forall \ n \in \mathcal {T}\\ &{} x_n \in \mathbb {Z}_+^{d_1}\times \mathbb {R}_+^{d_2} &{} \forall \ n \in \mathcal {T}. \end{array} \end{aligned}$$
(7.1)

Since the state variables are bounded by (A1), we can assume that \( x_{n} \in [0,U]^d\) for some positive integer U for all \(n \in \mathcal {T}\).

We approximate (7.1) as follows. For an integer state variable \(x \in \{0, \ldots ,U\}\), we substitute by its binary expansion: \(x = \sum _{i=1}^{\kappa } 2^{i-1} \lambda _i\) where \(\lambda _i \in \{0,1\}\) and \(\kappa = \lfloor \log _2 U \rfloor + 1\). For a continuous state variable \(x \in [0,U]\), we approximate it by binary approximation to a precision of \(\epsilon \in (0,1)\), i.e. \(x = \sum _{i=1}^{\kappa } 2^{i-1} \epsilon \lambda _i\) where \(\lambda _i \in \{0,1\}\) and \(\kappa = \lfloor \log _2 (U/\epsilon ) \rfloor + 1\) (see e.g., [35]). Note that \(|x - \sum _{i=1}^{\kappa } 2^{i-1} \epsilon \lambda _i | \le \epsilon \). The total number k of binary variables introduced to approximate the d state variables thus satisfies \(k \le d (\lfloor \log _2(U/\epsilon ) \rfloor + 1)\). We then have the following approximating MSIP with binary variables \(\lambda _n\in \{0,1\}^k\)

$$\begin{aligned} \begin{array}{rll} \displaystyle {\min _{\lambda _n, y_n} } &{} \displaystyle {\sum _{n \in \mathcal {T}} }p_n f_n(A\lambda _n,y_n) &{} \\ \mathrm{s.t.} &{} (A\lambda _{a(n)}, A\lambda _n, y_n) \in X_n &{} \forall \ n \in \mathcal {T}\\ &{} \lambda _n \in \{0,1\}^k &{} \forall \ n \in \mathcal {T}, \end{array} \end{aligned}$$
(7.2)

where the \(d \times k\) matrix A encodes the coefficients of the binary expansion.

Recall that the local variables are mixed integer, i.e. \(y_n = (u_n,v_n)\) with \(u_n \in \mathbb {Z}_+^{\ell _1}\) and \(v_n \in \mathbb {R}_+^{\ell _2}\). Given \(x := \{x_n\in \mathbb {Z}^{d_1}\times \mathbb {R}^{d_2}\}_{n\in \mathcal {T}}\), let

$$\begin{aligned}\begin{array}{ll} \phi (x) &{} := \displaystyle {\min _{u,v}}\left\{ \sum _{n\in \mathcal {T}}f_n(x_n,(u_n,v_n)): (x_{a(n)}, x_n, (u_n,v_n))\in X_n,~\forall n\in \mathcal {T}\right\} \\ &{} = \displaystyle {\sum _{n\in \mathcal {T}} \min _{u_n,v_n}}\left\{ f_n(x_n,(u_n,v_n)): (x_{a(n)}, x_n, (u_n,v_n))\in X_n\right\} \\ &{} = \displaystyle {\sum _{n\in \mathcal {T}} \min _{u_n\in {\mathcal {U}}_n}}\left\{ \psi _n(x_{a(n)},x_n,u_n)\right\} ,\\ \end{array} \end{aligned}$$

where

$$\begin{aligned} \psi _n(x_{a(n)},x_n,u_n) = \min _{v_n \in \mathbb {R}_+^{\ell _2}}\left\{ f_n(x_n, (u_n, v_n)): (x_{a(n)}, x_n, (u_n,v_n))\in X_n\right\} , \end{aligned}$$

and \({\mathcal {U}}_n\) is the finite set of integer values the local variable \(u_n\) can take. By the compactness assumption (A1) and the complete continuous recourse assumption (A2), the function \(\psi _n\) is the value function of a linear program that is feasible and bounded for all values of \((x_{a(n)},x_n,u_n)\). By Hoffman’s lemma [43], there exists a constant \(C_n(u_n)\) which is dependent on the data defining \((f_n,X_n)\) and \(u_n\), such that \(\psi _n(x_{a(n)},x_n,u_n)\) is Lipschitz continuous with respect to \((x_{a(n)},x_n)\) with this constant. It follows that \(\phi (x)\) is Lipschitz continuous with respect to x with constant \(C = \sum _{n\in T}\max _{u_n\in U_n}C_n(u_n)\), i.e.,

$$\begin{aligned} |\phi (x) - \phi (x')| \le C \Vert x - x'\Vert \;\; \forall \ x, x'. \end{aligned}$$

Let \((\tilde{\lambda }, \tilde{y})\) be an optimal solution to problem (7.2) and \(v_2\) be its optimal value. Define \(\tilde{x}_n = A\tilde{\lambda }_n\) for all \(n\in \mathcal {T}\), then \((\tilde{x}, \tilde{y})\) is a feasible solution to (7.1) and has the objective value of \(v_2\). From the definition of \(\phi \) we have that \(v_2 = \phi (\tilde{x})\). Now let \((\hat{x}, \hat{y})\) be an optimal solution of (7.1) and \(v_1\) be its optimal value. Note that \(v_1 = \phi (\hat{x})\). Let us construct a solution \((\hat{\lambda },\hat{y}')\) such that

$$\begin{aligned} \Vert \hat{x} - A\hat{\lambda }\Vert \le \sqrt{|\mathcal {T}|d} \epsilon , ~\text { and }~\hat{y}'_n = \displaystyle {{\text {argmin}}_{y_n}}\left\{ f(A\hat{\lambda }_{a(n)}, A\hat{\lambda }_n, y_n): (A\hat{\lambda }_{a(n)}, A\hat{\lambda }_n, y_n) {\in } X_n \right\} . \end{aligned}$$

Then \((\hat{\lambda },\hat{y}')\) is clearly a feasible solution to (7.2) and has the objective value \(\phi (A\hat{\lambda })\). Thus we have the following inequalities

$$\begin{aligned} \phi (\hat{x}) \le \phi (\tilde{x}) \le \phi (A\hat{\lambda }). \end{aligned}$$

Thus

$$\begin{aligned} 0 \le \phi (\tilde{x}) - \phi (\hat{x}) \le | \phi (A\hat{\lambda }) - \phi (\hat{x}) | \le C \Vert A\hat{\lambda } - \hat{x}\Vert \le C\sqrt{|\mathcal {T}|d} \epsilon = C' \sqrt{d}\epsilon , \end{aligned}$$

where \(C' = C\sqrt{|\mathcal {T}|}\). By choosing \(\epsilon = \varepsilon /C'\sqrt{d}\) and \(M = UC'\) we have that \((\tilde{x}, \tilde{y})\) is a \(\varepsilon \)-optimal solution of (7.1) and \(k \le d (\lfloor \log _2(M\sqrt{d}/\varepsilon ) \rfloor + 1)\) as desired. \(\square \)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zou, J., Ahmed, S. & Sun, X.A. Stochastic dual dynamic integer programming. Math. Program. 175, 461–502 (2019). https://doi.org/10.1007/s10107-018-1249-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-018-1249-5

Keywords

Mathematics Subject Classification

Search

Navigation