{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:16:41Z","timestamp":1760239001265,"version":"build-2065373602"},"reference-count":34,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2020,9,18]],"date-time":"2020-09-18T00:00:00Z","timestamp":1600387200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Independent System Operators (ISOs) worldwide face the ever-increasing challenge of coping with uncertainties, which requires sophisticated algorithms for solving unit-commitment (UC) problems of increasing complexity in less-and-less time. Hence, decomposition methods are appealing options to produce easier-to-handle problems that can hopefully return good solutions at reasonable times. When applied to two-stage stochastic models, decomposition often yields subproblems that are embarrassingly parallel. Synchronous parallel-computing techniques are applied to the decomposable subproblem and frequently result in considerable time savings. However, due to the inherent run-time differences amongst the subproblem\u2019s optimization models, unequal equipment, and communication overheads, synchronous approaches may underuse the computing resources. Consequently, asynchronous computing constitutes a natural enhancement to existing methods. In this work, we propose a novel extension of the asynchronous level decomposition to solve stochastic hydrothermal UC problems with mixed-integer variables in the first stage. In addition, we combine this novel method with an efficient task allocation to yield an innovative algorithm that far outperforms the current state-of-the-art. We provide convergence analysis of our proposal and assess its computational performance on a testbed consisting of 54 problems from a 46-bus system. Results show that our asynchronous algorithm outperforms its synchronous counterpart in terms of wall-clock computing time in 40% of the problems, providing time savings averaging about 45%, while also reducing the standard deviation of running times over the testbed in the order of 25%.<\/jats:p>","DOI":"10.3390\/a13090235","type":"journal-article","created":{"date-parts":[[2020,9,18]],"date-time":"2020-09-18T07:27:33Z","timestamp":1600414053000},"page":"235","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["A Mixed-Integer and Asynchronous Level Decomposition with Application to the Stochastic Hydrothermal Unit-Commitment Problem"],"prefix":"10.3390","volume":"13","author":[{"given":"Bruno","family":"Colonetti","sequence":"first","affiliation":[{"name":"Department of Electrical and Electronic Engineering, Federal University of Santa Catarina, Florian\u00f3polis 88040-900, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9181-0097","authenticated-orcid":false,"given":"Erlon Cristian","family":"Finardi","sequence":"additional","affiliation":[{"name":"Department of Electrical and Electronic Engineering, Federal University of Santa Catarina, Florian\u00f3polis 88040-900, Brazil"},{"name":"INESC P&amp;D Brasil, Bairro Gonzaga 11055-300, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Welington","family":"de Oliveira","sequence":"additional","affiliation":[{"name":"MINES ParisTech, CMA\u2014Centre de Math\u00e9matiques Appliqu\u00e9es, PSL\u2014Research University, Sophia Antipolis, 75006 Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,9,18]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1913","DOI":"10.1109\/TPWRS.2014.2355204","article-title":"Stochastic Optimization for Unit Commitment\u2014A Review","volume":"30","author":"Zheng","year":"2015","journal-title":"IEEE Trans. Power Syst."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"106709","DOI":"10.1016\/j.epsr.2020.106709","article-title":"Hourly Pricing and Day-Ahead Dispatch Setting in Brazil: The Dessem Model","volume":"189","author":"Santos","year":"2020","journal-title":"Electr. Power Syst. Res."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Chen, Y., Pan, F., Holzer, J., Rothberg, E., Ma, Y., and Veeramany, A. (2020). A High Performance Computing Based Market Economics Driven Neighborhood Search and Polishing Algorithm for Security Constrained Unit Commitment. IEEE Trans. Power Syst., 1.","DOI":"10.1109\/TPWRS.2020.3005407"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/s10288-014-0279-y","article-title":"Large-Scale Unit Commitment under Uncertainty","volume":"13","author":"Tahanan","year":"2015","journal-title":"4OR"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Birge, J.R., and Louveaux, F. (2011). Introduction to Stochastic Programming, Springer New York.","DOI":"10.1007\/978-1-4614-0237-4"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1016\/j.ijepes.2019.01.037","article-title":"Fundamentals and Recent Developments in Stochastic Unit Commitment","volume":"109","year":"2019","journal-title":"Int. J. Electr. Power Energy Syst."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/s10107-012-0570-7","article-title":"Divide to Conquer: Decomposition Methods for Energy Optimization","volume":"134","year":"2012","journal-title":"Math. Program."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1007\/BF01386316","article-title":"Partitioning Procedures for Solving Mixed-Variables Programming Problems","volume":"4","author":"Benders","year":"1962","journal-title":"Numer. Math."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"462","DOI":"10.1080\/10556788.2018.1496431","article-title":"A Sharp Augmented Lagrangian-Based Method in Constrained Non-Convex Optimization","volume":"34","author":"Bagirov","year":"2019","journal-title":"Optim. Methods Softw."},{"key":"ref_10","unstructured":"Bertsekas, D.P., and Tsitsiklis, J.N. (2015). Parallel and Distributed Computation: Numerical Methods, Athena Scientific."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1109\/TSTE.2017.2719659","article-title":"A Fully Parallel Stochastic Multiarea Power System Operation Considering Large-Scale Wind Power Integration","volume":"9","author":"Khanabadi","year":"2018","journal-title":"IEEE Trans. Sustain. Energy"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1109","DOI":"10.1109\/TPWRS.2014.2341354","article-title":"Applying High Performance Computing to Transmission-Constrained Stochastic Unit Commitment for Renewable Energy Integration","volume":"30","author":"Papavasiliou","year":"2015","journal-title":"IEEE Trans. Power Syst."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1925","DOI":"10.1109\/TPWRS.2014.2360063","article-title":"Distributed Security-Constrained Unit Commitment for Large-Scale Power Systems","volume":"30","author":"Kargarian","year":"2015","journal-title":"IEEE Trans. Power Syst."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"3981","DOI":"10.1109\/TPWRS.2017.2787645","article-title":"Decentralized Implementation of Unit Commitment With Analytical Target Cascading: A Parallel Approach","volume":"33","author":"Kargarian","year":"2018","journal-title":"IEEE Trans. Power Syst."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1137\/17M1148189","article-title":"An Asynchronous Bundle-Trust-Region Method for Dual Decomposition of Stochastic Mixed-Integer Programming","volume":"29","author":"Kim","year":"2019","journal-title":"SIAM J. Optim."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Kim, K., Anitescu, M., and Zavala, V.M. (2018). An Asynchronous Decomposition Algorithm for Security Constrained Unit Commitment Under Contingency Events. Proceedings of the 2018 Power Systems Computation Conference (PSCC), IEEE.","DOI":"10.23919\/PSCC.2018.8450937"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Aravena, I., and Papavasiliou, A. (2015). A Distributed Asynchronous Algorithm for the Two-Stage Stochastic Unit Commitment Problem. Proceedings of the 2015 IEEE Power & Energy Society General Meeting, IEEE.","DOI":"10.1109\/PESGM.2015.7285913"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1504","DOI":"10.1109\/TSG.2016.2593402","article-title":"A New Nested Benders Decomposition Strategy for Parallel Processing Applied to the Hydrothermal Scheduling Problem","volume":"8","author":"Santos","year":"2017","journal-title":"IEEE Trans. Smart Grid"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"4888","DOI":"10.1109\/TPWRS.2012.2236654","article-title":"An Efficient Parallel Algorithm for Large Scale Hydrothermal System Operation Planning","volume":"28","author":"Pinto","year":"2013","journal-title":"IEEE Trans. Power Syst."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Moritsch, H.W., Pflug, G.C., and Siomak, M. (2001). Asynchronous Nested Optimization Algorithms and Their Parallel Implementation. Wuhan Univ. J. Nat. Sci.","DOI":"10.1007\/BF03160302"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"801","DOI":"10.1016\/j.ejor.2016.12.005","article-title":"The Benders Decomposition Algorithm: A Literature Review","volume":"259","author":"Rahmaniani","year":"2017","journal-title":"Eur. J. Oper. Res."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Kelley, J.E. (1960). The Cutting-Plane Method for Solving Convex Programs. J. Soc. Ind. Appl. Math.","DOI":"10.1137\/0108053"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Bagirov, A., Karmitsa, N., and M\u00e4kel\u00e4, M.M. (2014). Introduction to Nonsmooth Optimization, Springer International Publishing.","DOI":"10.1007\/978-3-319-08114-4"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1016\/j.ejor.2014.05.010","article-title":"Applying Oracles of On-Demand Accuracy in Two-Stage Stochastic Programming\u2014A Computational Study","volume":"239","author":"Wolf","year":"2014","journal-title":"Eur. J. Oper. Res."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Van Ackooij, W., Frangioni, A., and de Oliveira, W. (2016). Inexact Stabilized Benders\u2019 Decomposition Approaches with Application to Chance-Constrained Problems with Finite Support. Comput. Optim. Appl.","DOI":"10.1007\/s10589-016-9851-z"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"957","DOI":"10.1007\/978-3-030-21803-4_95","article-title":"Robust Design of Pumping Stations in Water Distribution Networks","volume":"Volume 991","author":"Bonvin","year":"2020","journal-title":"Advances in Intelligent Systems and Computing"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"M\u00e4kel\u00e4, M.M., Karmitsa, N., and Bagirov, A. (2013). Subgradient and Bundle Methods for Nonsmooth Optimization, Springer.","DOI":"10.1007\/978-94-007-5288-7_15"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Bagirov, A.M., Gaudioso, M., Karmitsa, N., M\u00e4kel\u00e4, M.M., and Taheri, S. (2020). Numerical Nonsmooth Optimization, Springer International Publishing.","DOI":"10.1007\/978-3-030-34910-3"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Lemar\u00e9chal, C., Nemirovskii, A., and Nesterov, Y. (1995). New Variants of Bundle Methods. Math. Program.","DOI":"10.1007\/BF01585555"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1007\/s11750-016-0413-4","article-title":"Regularized Optimization Methods for Convex MINLP Problems","volume":"24","year":"2016","journal-title":"TOP"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Iutzeler, F., Malick, J., and de Oliveira, W. (2019). Asynchronous Level Bundle Methods. Math. Program.","DOI":"10.1007\/s10107-019-01414-y"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"795","DOI":"10.1137\/120865987","article-title":"A Parallel Bundle Framework for Asynchronous Subspace Optimization of Nonsmooth Convex Functions","volume":"24","author":"Fischer","year":"2014","journal-title":"SIAM J. Optim."},{"key":"ref_33","unstructured":"Gurobi Optimization LLC (2018). Gurobi Optimizer Reference Manual, Gurobi Optimization LLC."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/s101070100263","article-title":"Benchmarking Optimization Software with Performance Profiles","volume":"91","author":"Dolan","year":"2002","journal-title":"Math. Program."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/9\/235\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:11:11Z","timestamp":1760177471000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/9\/235"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,18]]},"references-count":34,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2020,9]]}},"alternative-id":["a13090235"],"URL":"https:\/\/doi.org\/10.3390\/a13090235","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2020,9,18]]}}}