A Revolutionary Way to Tackle Challenging MILP Problems in Power Systems through Accelerated Convergence, Formulation Tightening and Asynchronous Optimization

通过加速收敛、公式紧缩和异步优化来解决电力系统中具有挑战性的 MILP 问题的革命性方法

• 批准号: 1810108
• 负责人: Zongjie Wang
• 金额: $ 36万
• 依托单位: University of Connecticut
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-08-15 至 2023-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1810108&HistoricalAwards=false
• 关键词: Revolutionary; Way; Tackle; Challenging; MILP

Many important optimization problems in power systems are formulated as Mixed-Integer Linear Programming (MILP, with integer and continues variables and a linear structure) problems. Because of the existence of integer variables, problem complexity generally increases exponentially as the problem size increases. One important example is Unit Commitment and Economic Dispatch (UCED) with complicated units that are difficult to handle, e.g., combined cycle units. We have witnessed the breakdown of existing methods on large-scale UCED cases. The problem is further complicated by the significant increase of distributed generation, including intermittent renewables, making it very difficult to solve, and pushing for a centralized/decentralized hybrid grid architecture. This project seeks to revolutionize the way how complicated MILP problems are formulated and solved within a decomposition and coordination framework, exploiting the exponential decrease of complexity upon decomposition and uses our recent breakthrough on effective coordination. Using UCED as the problem context, Task 1 is on developing a novel and systematic approach, to tighten MILP formulations. In the extreme case, a problem's constraints directly delineate its "convex hull," and the "NP-hard" problem can be solved by using linear programming methods without difficulties. To solve practical problems within the decomposition and coordination framework, the focus is on obtaining "near tight" formulations of single units. Motivated by the foreseeable transitioning from a centralized grid toward a hybrid grid, in Task 2, a distributed and asynchronous coordination method will be investigated with subproblems solved in a distributed way and prices updated asynchronously. The intellectual merit is on the revolutionary way to formulate and solve MILP problems - not just to describe constraints, but to transform them to a "near-tight" form, and to exploit exponential decrease of complexity via decomposition plus effective and asynchronous coordination. The research will have broader impacts on other MILP problems in power systems and beyond, e.g., distribution networks, self-optimizing factories, autonomous and coordinated systems; and on nonlinear problems with separable structures. The research will also educate graduate, undergraduate and professionals through courses, seminars, publications and online materials, and impact high school students through UConn's da Vinci summer program.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

电力系统中的许多重要优化问题都被表述为混合整数线性规划（MILP，具有整数和连续变量以及线性结构）问题。由于整数变量的存在，问题复杂度一般随着问题规模的增大而呈指数级增长。 一个重要的例子是机组承诺和经济调度（UCED），其复杂的机组难以处理，例如联合循环机组。我们目睹了现有方法在大规模 UCED 案例中的崩溃。由于分布式发电（包括间歇性可再生能源）的显着增加，使得问题变得非常难以解决，并推动集中/分散混合电网架构，这使得问题变得更加复杂。该项目旨在彻底改变在分解和协调框架内制定和解决复杂 MILP 问题的方式，利用分解后复杂性的指数下降，并利用我们最近在有效协调方面的突破。 使用 UCED 作为问题背景，任务 1 是开发一种新颖的系统方法，以加强 MILP 公式。在极端情况下，问题的约束直接描绘出它的“凸包”，并且“NP难”问题可以使用线性规划方法毫无困难地解决。为了在分解和协调框架内解决实际问题，重点是获得单个单元的“近紧”公式。受可预见的从集中式电网向混合电网过渡的推动，在任务 2 中，将研究分布式异步协调方法，以分布式方式解决子问题并异步更新价格。其智力价值在于以革命性的方式制定和解决 MILP 问题 - 不仅仅是描述约束，而是将它们转换为“近紧”形式，并通过分解加上有效的异步协调来实现复杂性的指数下降。该研究将对电力系统及其他领域的其他 MILP 问题产生更广泛的影响，例如配电网络、自优化工厂、自治和协调系统；以及可分离结构的非线性问题。该研究还将通过课程、研讨会、出版物和在线材料对研究生、本科生和专业人士进行教育，并通过康涅狄格大学的达芬奇暑期项目影响高中生。该奖项反映了 NSF 的法定使命，并通过使用基金会的评估进行评估，认为值得支持。智力价值和更广泛的影响审查标准。

项目成果

TSO-DSO Operational Planning Coordination Through “$l_1-$Proximal” Surrogate Lagrangian Relaxation

• DOI: 10.1109/tpwrs.2021.3101220
• 发表时间: 2021-01
• 期刊: IEEE Transactions on Power Systems
• 影响因子: 6.6
• 作者: Mikhail A. Bragin;Y. Dvorkin

Distributed and Asynchronous Coordination of a Mixed-Integer Linear System via Surrogate Lagrangian Relaxation

• DOI: 10.1109/tase.2020.2998048
• 发表时间: 2021-07-01
• 期刊: IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING
• 影响因子: 5.6
• 作者: Bragin, Mikhail A.;Yan, Bing;Luh, Peter B.
• 通讯作者: Luh, Peter B.

Impacts of UC Formulation Tightening on Computation of Convex Hull Prices

UC 公式紧缩对凸包价格计算的影响

• DOI: 10.1109/pesgm46819.2021.9638016
• 发表时间: 2021
• 期刊: IEEE Power and Energy Society General Meeting
• 作者: F. Hyder, B. Yan

Tightened Formulation and Resolution of Energy-Efficient Job-Shop Scheduling

• DOI: 10.1109/case48305.2020.9217035
• 发表时间: 2020-08
• 期刊: 2020 IEEE 16th International Conference on Automation Science and Engineering (CASE)
• 作者: B. Yan;Mikhail A. Bragin;P. Luh

Effects of Tightening Unit-level and System-level Constraints in Unit Commitment,

收紧单位级和系统级约束对单位承诺的影响，

• 发表时间: 2019
• 期刊: IEEE Power & Energy Society General Meeting
• 作者: Yan, Bing;Luh, Peter B.;Litvinov, Eugene;Zheng, Tongxin;Schiro, Dane;Bragin, Mikhail A.;Zhao, Feng;Zhao, Jinye;Lelic, Izudin
• 通讯作者: Lelic, Izudin