Collaborative Research: Next-Generation Cutting Planes: Compression, Automation, Diversity, and Computer-Assisted Mathematics

混合整数优化是一种强大的数学决策技术，涉及运筹学、数据科学和人工智能。该项目考虑需要快速做出高风险决策并考虑未知未来事件或风险的应用。在这样的应用中，模拟方法和机器学习不能提供足够的信心来防止灾难性故障的可能性。相反，需要多参数优化来预先计算响应，验证其安全性，并保证性能水平。在这个方向上，研究人员将研究优化算法的关键组成部分，称为通用切割平面，适用于化学工程过程控制的新型多参数设置和高性能计算平台的优化编译器，旨在取得将推广到许多重要应用的重大理论和计算进展。更广泛的影响包括对本科生和研究生在计算数学和研究技能方面的培训，以及高质量开源研究软件的开发，以及数学、计算机科学和工程领域几个研究团体之间的进一步联系。混合整数（线性和非线性）优化涉及有限维的非凸优化问题，其中包括离散决策变量，例如那些模拟“是/否”决策的决策变量。这种类型的系统出现在工业和科学的所有领域。混合整数优化算法建立在通过松弛、近似、凸化和分解技术的凸优化技术之上。在大数据技术的存在下，系统规模的增加带来了新的挑战，需要通过下一代算法来解决。本课题从压缩、自动化、多样性等方面研究凸化，即多排、多切口切割平面系统中有效、高效的切割平面。特别地，计算具有规定特征的极值连续分段线性切割生成函数的空间；它们由半代数单元组成，参数化次加性分段线性函数，粘在它们的边界上。每个单元的计算都需要定理的证明，基于元编程和半代数计算的自动化定理证明技术将得到发展。研究人员将把新的切割平面技术应用于两个目标应用，保证其正确性和性能是关键任务：化学过程工程中的模型预测控制和高性能计算平台的优化编译器。这两种应用中的多参数优化问题将受益于新切割平面的参数化特性。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Mixed-integer optimization is a powerful mathematical decision-making technology related to operations research, data sciences, and artificial intelligence. This project considers applications in which high-stake decisions need to be made quickly and account for unknown future event or risk. In such applications, simulation methods and machine learning cannot give sufficient confidence for protecting against the possibility of catastrophic failures. Instead, one requires multi-parametric optimization to precompute responses, certify their safety, and guarantee the level of performance. In this direction, the investigators will study a key component of optimization algorithms called general purpose cutting planes in a novel multi-parametric setting suitable for process control in chemical engineering and optimizing compilers for high-performance computing platforms, aiming for major theoretical and computational advances that will generalize to many important applications. Broader impacts include the training of undergraduate and graduate students in computational mathematics and research skills, as well as development of high-quality open-source research software, and of further connections between several research communities within mathematics, computer science, and engineering.Mixed-integer (linear and nonlinear) optimization is concerned with finite-dimensional, non-convex optimization problems that include discrete decision variables such as those that model "yes/no" decisions. Systems of this type arise in all areas of industry and the sciences. Algorithms for mixed-integer optimization build upon convex optimization technology by relaxation, approximation, convexification, and decomposition techniques. Increases in system size in the presence of Big Data technologies creates new challenges that need to be addressed by a next generation of algorithms. This project studies convexification, specifically, cutting planes in multi-row and multi-cut cutting plane systems that are effective and efficient from the aspects of compression, automation, and diversity. In particular, spaces of extreme continuous piecewise linear cut-generating functions with prescribed features will be computed; these consist of semi-algebraic cells, parametrizing sub-additive piecewise linear functions, glued at their boundaries. The computation of each cell requires the proof of a theorem, and automated theorem proving technology, based on metaprogramming and semi-algebraic computations, will be developed. The investigators will apply the new cutting plane techniques to two target applications for which guaranteed correctness and performance is mission-critical: model predictive control in chemical process engineering and optimizing compilers for high-performance computing platforms. The multi-parametric optimization problems in both applications will benefit from the parametric nature of the new cutting planes.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.