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

点击翻译按钮获取中文摘要

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.