权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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.

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