Automated decomposition of optimization problems through learning network structures

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

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.