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

合作研究：下一代切割面：压缩、自动化、多样性和计算机辅助数学

基本信息

批准号：
2012764
负责人：
Matthias Koeppe
金额：
$ 18.02万
依托单位：
University of California-Davis
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-08-01 至 2024-07-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2012764&HistoricalAwards=false
关键词：
Collaborative Research Next Generation Cutting

项目摘要

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.

混合企业优化是与运营研究，数据科学和人工智能有关的强大数学决策技术。该项目考虑了需要快速做出高级决策的申请，并考虑未知的未来事件或风险。在这样的应用中，模拟方法和机器学习不能给予足够的信心来防止灾难性失败的可能性。取而代之的是，需要多参数优化来预先计算响应，证明其安全性并确保绩效水平。在这个方向上，调查人员将研究优化算法的关键组成部分，称为通用切割平面在新型的多参数设置中，适用于化学工程中的过程控制，并优化用于高性能计算平台的编译器这将推广到许多重要的应用程序。更广泛的影响包括对计算数学和研究技能的本科和研究生的培训，以及开发高质量的开源研究软件，以及数学，计算机科学和工程学中几个研究社区之间的进一步联系。整数（线性和非线性）优化涉及有限维的非凸优化问题，其中包括离散决策变量，例如模拟“是/否”决策的变量。这种类型的系统在行业和科学领域都出现。混合企业优化的算法通过放松，近似，凸化和分解技术建立在凸优化技术的基础上。在大数据技术的存在下，系统大小的增加会带来新的挑战，需要通过下一代算法来解决。该项目研究了凸化化，具体来说，在压缩，自动化和多样性方面有效而有效的多行和多切割平面系统中的切割平面。特别是，将计算具有规定功能的极端连续分段线性切割生成功能的空间；这些由半代数细胞组成，参数化亚addize分段线性函数，粘在其边界上。每个单元格的计算需要一个定理的证明，并且将基于元编程和半代数计算的自动定理证明技术。调查人员将将新的切割平面技术应用于两个目标应用程序，保证正确性和性能至关重要：化学过程工程中的模型预测控制以及为高性能计算平台优化编译器。这两种应用中的多参数优化问题将受益于新切割平面的参数性质。该奖项反映了NSF的法定任务，并且使用基金会的知识分子优点和更广泛的影响评估标准，被认为值得通过评估来获得支持。