A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
Advanced Search
Volume 9 Issue 7
Jul.  2022

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 15.3, Top 1 (SCI Q1)
    CiteScore: 23.5, Top 2% (Q1)
    Google Scholar h5-index: 77， TOP 5
Turn off MathJax
Article Contents
Article Navigation >  IEEE/CAA Journal of Automatica Sinica  > 2022  >  9(7): 1295-1306
Y. F. Zhang, F. Liu, Y. F. Su, Y. Chen, Z. J. Wang, and J. P. S. Catalão, “Two-stage robust optimization under decision dependent uncertainty,” IEEE/CAA J. Autom. Sinica, vol. 9, no. 7, pp. 1295–1306, Jul. 2022. doi: 10.1109/JAS.2022.105512
Citation: Y. F. Zhang, F. Liu, Y. F. Su, Y. Chen, Z. J. Wang, and J. P. S. Catalão, “Two-stage robust optimization under decision dependent uncertainty,” IEEE/CAA J. Autom. Sinica, vol. 9, no. 7, pp. 1295–1306, Jul. 2022. doi: 10.1109/JAS.2022.105512
shu

Two-Stage Robust Optimization Under Decision Dependent Uncertainty

doi: 10.1109/JAS.2022.105512
  • 1.

    State Key Laboratory of Power System and Generation Equipment, the Department of Electrical Engineering, Tsinghua University, Beijing 100084, China

  • 2.

    Department of Mechanical and Automation Engineering, the Chinese University of Hong Kong, Hong Kong SAR, China

  • 3.

    Ministry of Education Key Laboratory of System Control and Information Processing, the Department of Automation, Shanghai Jiao Tong University, Shanghai 200240, China

  • 4.

    Shanghai Engineering Research Center of Intelligent Control and Management, Shanghai 200240, China

  • 5.

    Faculty of Engineering of the University of Porto and Institute for Systems and Computer Engineering, Technology and Science (INESC TEC), Porto 4200-465, Portugal

Funds:  This work was supported by the Joint Research Fund in Smart Grid under cooperative agreement between the National Natural Science Foundation of China (NSFC) and State Grid Corporation of China (U1966601)
More Information
    Abstract
  • In the conventional robust optimization (RO) context, the uncertainty is regarded as residing in a predetermined and fixed uncertainty set. In many applications, however, uncertainties are affected by decisions, making the current RO framework inapplicable. This paper investigates a class of two-stage RO problems that involve decision-dependent uncertainties. We introduce a class of polyhedral uncertainty sets whose right-hand-side vector has a dependency on the here-and-now decisions and seek to derive the exact optimal wait-and-see decisions for the second-stage problem. A novel iterative algorithm based on the Benders dual decomposition is proposed where advanced optimality cuts and feasibility cuts are designed to incorporate the uncertainty-decision coupling. The computational tractability, robust feasibility and optimality, and convergence performance of the proposed algorithm are guaranteed with theoretical proof. Four motivating application examples that feature the decision-dependent uncertainties are provided. Finally, the proposed solution methodology is verified by conducting case studies on the pre-disaster highway investment problem.

     

    • FullText(HTML)
  • loading
    • References(31)
  • [1]
    A. Ben-Tal and A. Nemirovski, “Robust solutions of uncertain linear programs,” Oper. Res. Lett., vol. 25, no. 1, pp. 1–13, 1999. doi: 10.1016/S0167-6377(99)00016-4
    [2]
    Y. Chen, W. Wei, F. Liu, and S. Mei, “Distributionally robust hydrothermal-wind economic dispatch,” Appl. Energy, vol. 173, pp. 511–519, 2016. doi: 10.1016/j.apenergy.2016.04.060
    [3]
    N. H. Lappas and C. E. Gounaris, “Robust optimization for decisionmaking under endogenous uncertainty,” Comput. Chem. Eng., vol. 111, pp. 252–266, 2018. doi: 10.1016/j.compchemeng.2018.01.006
    [4]
    N. H. Lappas and C. E. Gounaris, “The use of decision-dependent uncertainty sets in robust optimization,” in Proc. Foundations of Computer-Aided Process Operations/Chemical Process Control, 2017.
    [5]
    N. H. Lappas and C. E. Gounaris, “Multi-stage adjustable robust optimization for process scheduling under uncertainty,” AIChE Journal, vol. 62, no. 5, pp. 1646–1667, 2016. doi: 10.1002/aic.15183
    [6]
    R. Vujanic, P. Goulart, and M. Morari, “Robust optimization of schedules affected by uncertain events,” J. Optim. Theory Appl., vol. 171, no. 3, pp. 1033–1054, 2016. doi: 10.1007/s10957-016-0920-3
    [7]
    C. Wang, F. Liu, J. Wang, F. Qiu, W. Wei, S. Mei, and S. Lei, “Robust risk-constrained unit commitment with large-scale wind generation: An adjustable uncertainty set approach,” IEEE Trans. Power Syst., vol. 32, no. 1, pp. 723–733, Jan. 2017. doi: 10.1109/TPWRS.2016.2564422
    [8]
    X. Zhang, M. Kamgarpour, A. Georghiou, P. Goulart, and J. Lygeros, “Robust optimal control with adjustable uncertainty sets,” Automatica, vol. 75, pp. 249–259, 2017. doi: 10.1016/j.automatica.2016.09.016
    [9]
    Y. Su, Y. Zhang, F. Liu, S. Feng, Y. Hou, and W. Wang, “Robust dispatch with demand response under decision-dependent uncertainty,” in Proc. IEEE Sustainable Power and Energy Conf., 2020, pp. 2122–2127.
    [10]
    M. Daneshvar, B. Mohammadi-Ivatloo, K. Zare, and S. Asadi, “Twostage robust stochastic model scheduling for transactive energy based renewable microgrids,” IEEE Trans. Ind. Informat., vol. 16, no. 11, pp. 6857–6867, Nov. 2020. doi: 10.1109/TII.2020.2973740
    [11]
    M. Johnston, H. Lee, and E. Modiano, “A robust optimization approach to backup network design with random failures,” IEEE/ACM Trans. Netw., vol. 23, no. 4, pp. 1216–1228, Aug. 2015. doi: 10.1109/TNET.2014.2320829
    [12]
    K. Park, J. Kim, H. Lim, and Y. Eun, “Robust path diversity for network quality of service in cyber-physical systems,” IEEE Trans. Ind. Informat., vol. 10, no. 4, pp. 2204–2215, Nov. 2014. doi: 10.1109/TII.2014.2351753
    [13]
    V. Goel and I. E. Grossmann, “A class of stochastic programs with decision dependent uncertainty,” Math. Program., vol. 108, no. 2, pp. 355–394, 2006.
    [14]
    M. Poss, “Robust combinatorial optimization with variable budgeted uncertainty,” 4OR – A Quarterly J. Operations Research, vol. 11, no. 1, pp. 75–92, 2013. doi: 10.1007/s10288-012-0217-9
    [15]
    M. Poss, “Robust combinatorial optimization with variable cost uncertainty,” Eur. J. Oper. Res., vol. 237, no. 3, pp. 836–845, 2014. doi: 10.1016/j.ejor.2014.02.060
    [16]
    O. Nohadani and K. Sharma, “Optimization under decision-dependent uncertainty,” SIAM J. Optim., vol. 28, no. 2, pp. 1773–1795, 2018. doi: 10.1137/17M1110560
    [17]
    A. Ben-Tal, A. Goryashko, E. Guslitzer, and A. Nemirovski, “Adjustable robust solutions of uncertain linear programs,” Math. Program., vol. 99, no. 2, pp. 351–376, 2004. doi: 10.1007/s10107-003-0454-y
    [18]
    P. Hansen, B. Jaumard, and G. Savard, “New branch-and-bound rules for linear bilevel programming,” SIAM J. Sci. Statist. Comput., vol. 13, no. 5, pp. 1194–1217, 1992. doi: 10.1137/0913069
    [19]
    N. H. Lappas and C. E. Gounaris, “Theoretical and computational comparison of continuous-time process scheduling models for adjustable robust optimization,” AIChE Journal, vol. 64, no. 8, pp. 3055–3070, 2018. doi: 10.1002/aic.16124
    [20]
    W. Feng, Y. Feng, and Q. Zhang, “Multistage robust mixed-integer optimization under endogenous uncertainty,” Eur. J. Oper. Res., vol. 294, no. 2, pp. 460–475, 2020.
    [21]
    Q. Zhang and W. Feng, “A unified framework for adjustable robust optimization with endogenous uncertainty,” AIChE Journal, vol. 66, p. e.17047, 2020.
    [22]
    S. Avraamidou and E. N. Pistikopoulos, “Adjustable robust opti- mization through multi-parametric programming,” Optim. Lett., vol. 14, no. 4, pp. 873–887, 2020. doi: 10.1007/s11590-019-01438-5
    [23]
    L. Zhao and B. Zeng, “Robust unit commitment problem with demand response and wind energy,” in Proc. IEEE Power and Energy Soc. Gen. Meeting, 2012, pp. 1–8.
    [24]
    B. Zeng and L. Zhao, “Solving two-stage robust optimization problems using a column-and-constraint generation method,” Oper. Res. Lett., vol. 41, no. 5, pp. 457–461, 2013. doi: 10.1016/j.orl.2013.05.003
    [25]
    R. Jiang, M. Zhang, G. Li, and Y. Guan, “Benders’ decomposition for the two-stage security constrained robust unit commitment problem,” in Proc. IIE Annual Conf., 2012, pp. 3332–3341.
    [26]
    D. Bertsimas, E. Litvinov, X. A. Sun, J. Zhao, and T. Zheng, “Adaptive robust optimization for the security constrained unit commitment problem,” IEEE Trans. Power Syst., vol. 28, no. 1, pp. 52–63, Feb. 2013. doi: 10.1109/TPWRS.2012.2205021
    [27]
    J. Benders, “Partitioning procedures for solving mixed-variables programming problems,” Numer Math (Heidelb), vol. 4, no. 1, pp. 238–252, 1962. doi: 10.1007/BF01386316
    [28]
    S. Peeta, F. Salman, D. Gunnec, and K. Viswanath, “Pre-disaster investment decisions for strengthening a highway network,” Comput. Oper. Res., vol. 37, pp. 1708–1719, 2010. doi: 10.1016/j.cor.2009.12.006
    [29]
    A. Baringo, L. Baringo, and J. M. Arroyo, “Day-ahead self-scheduling of a virtual power plant in energy and reserve electricity markets under uncertainty,” IEEE Trans. Power Syst., vol. 34, no. 3, pp. 1881–1894, May 2019. doi: 10.1109/TPWRS.2018.2883753
    [30]
    T. L. Magnanti and R. T. Wong, “Accelerating benders decomposition: Algorithmic enhancement and model selection criteria,” Oper. Res., vol. 29, no. 3, pp. 464–484, 1981. doi: 10.1287/opre.29.3.464
    [31]
    H. Konno, “A cutting plane algorithm for solving bilinear programs,” Math. Program., vol. 11, no. 1, pp. 14–27, 1976. doi: 10.1007/BF01580367
    • Related Articles
    • Supplements(0)

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(4)  / Tables(4)

    Get Citation
    PDF
    XML

    Article Metrics

    Article views (1276) PDF downloads(118) Cited by()

    Highlights

    • This paper investigates a class of two-stage robust optimization (RO) problems that involve decision-dependent uncertainties (DDUs). We introduce a class of polyhedral uncertainty sets whose right-hand-side vector has a dependency on the here-and-now decisions and seek to derive the exact optimal wait-and-see decisions for the second-stage problem. Conventional cutting-plane algorithms, including the renowned column-and-constraint generation algorithm, are no more applicable due to the possible failure in robust feasibility, optimality, and finite convergence
    • To solve the two-stage RO model with DDUs, we propose a novel iterative solution algorithm involving one master problem and two subproblems, based on Benders dual decomposition. Advanced optimality cuts and feasibility cuts are designed to accommodate the coupling between uncertain parameters and decision variables. Performance of the proposed algorithm, including the robust feasibility, robust optimality, and finite convergence, is guaranteed with strict proof
    • The proposed model and solution algorithm cater for a variety of application problems. Four motivating DDU-featured examples are provided in this paper, including a batch scheduling problem, the shortest path over an uncertain network problem, a frequency reserve provision problem, and a pre-disaster highway network investment problem. For the last application, pre-disaster network investment, numerical case studies are provided to verify the efficiency of the proposed method

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return