Automated decomposition of optimization problems through learning network structures

University Of Minnesota-Twin Cities, Minneapolis MN

Investigators

Abstract

Large-scale complex optimization problems have become increasingly important for control or dynamic optimization of chemical processes, including design or operation in an uncertain economic environment and integration of process design, control and scheduling at the enterprise-wide level. These problems are inherently non-scalable and computationally difficult to solve. Decomposition is a type of solution method where the larger problem is "decomposed" into multiple, easier-to-solve sub-problems. Decomposition based solution methods are computationally efficient for solving large optimization problems, but they rely on intuition for decomposing the optimization formulation into a set of interacting sub-problems that can be solved iteratively to obtain the optimum. The proposed research project aims to generalize this approach and eliminate the need for applying heuristics (intuition) by developing an automated framework for determining the most suitable decomposition structure and corresponding solution method. The proposed research aims to develop a generic framework for learning the underlying structure of a complex optimization problem, finding the corresponding decomposition consistent with this structure, and adapting the decomposition to account for integer variables and nonconvex constraints to improve the corresponding solution strategy. The developed framework will be automated through the development of open-source software packages for analyzing the structure of optimization problems and executing decomposition-based algorithms based on high-level programming languages. A stochastic block model will be introduced as a powerful statistical inference tool for analyzing network representations (variable-constraint graphs) of optimization problems. Within this framework, the most suitable block structure underlying the optimization problem topology (community structure, core-periphery structure, or hybrid structure) will be systematically determined, it will be refined to accommodate integer variables and nonconvex constraints and will be matched with the corresponding decomposition-based solution algorithms. Graduate students will be trained in fundamental research cutting across mathematics, optimization and network science. Undergraduate research projects inspired from this research projects will be offered as honors thesis research projects to undergraduate students at the University of Minnesota. The PI will mentor and host students from DeLaSalle High School in Minneapolis, which has a diverse student population, to cultivate their interest in pursuing STEM careers. 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.