Automated decomposition of optimization problems through learning network structures

大规模的复杂优化问题对于化工过程的控制或动态优化变得越来越重要，包括在不确定的经济环境中的设计或操作，以及整个企业层面的过程设计、控制和调度的集成。这些问题本质上是不可伸缩的，而且在计算上很难解决。分解是一种解决方法，它将较大的问题“分解”成多个更容易解决的子问题。基于分解的求解方法在求解大型优化问题时计算效率很高，但它们依赖于直觉将优化公式分解为一组相互作用的子问题，这些子问题可以迭代求解以获得最优解。该研究项目旨在推广该方法，并通过开发确定最适合的分解结构和相应的求解方法的自动化框架来消除应用启发式(直觉)的需要；该研究旨在开发一个通用框架，用于学习复杂优化问题的底层结构，找到与该结构一致的对应分解，并调整分解以考虑整数变量和非凸约束以改进相应的求解策略。所开发的框架将通过开发用于分析优化问题的结构和执行基于高级编程语言的分解算法的开放源码软件包来实现自动化。随机区块模型将被引入作为分析优化问题的网络表示(变量约束图)的强大统计推理工具。在这个框架内，系统地确定最适合优化问题拓扑结构的块结构(社区结构、核心-外围结构或混合结构)，并对其进行细化以适应整数变量和非凸约束，并与相应的基于分解的求解算法相匹配。研究生将接受跨越数学、优化和网络科学的基础研究培训。受此研究项目启发的本科生研究项目将作为荣誉论文研究项目提供给明尼苏达大学的本科生。PI将指导和接待明尼阿波利斯DeLaSalle高中的学生，以培养他们追求STEM职业生涯的兴趣。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.