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

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

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.