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.

电力系统中许多重要的优化问题都可以归结为具有整数和连续变量以及线性结构的混合线性规划问题。由于整数变量的存在，问题的复杂性通常会随着问题规模的增加而呈指数级增加。 一个重要的例子是机组组合和经济调度（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

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

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