CAREER: Theoretical and Computational Advances for Enabling Robust Numerical Guarantees in Linear and Mixed Integer Programming Solvers

数学规划是一种系统的解决问题的方法，它利用数学模型和算法来做出最佳决策，并受到一组给定的限制。在过去的三十年里，这个工具集在理论和应用方面取得了显着的进步，加上计算能力的同样令人印象深刻的加速，帮助优化软件在科学，工程，商业等领域的使用激增。然而，在实践中使用的商业优化求解器往往缺乏严格的数值保证，这在很大程度上不为用户所知，可能会导致他们返回不一致的结果。这样的结果可能导致从业者对正在分析的问题或系统得出错误的结论，并最终导致误导和错误的决策。这些和其他不正确结果的不可预测性和不可忽略的可预测性，可以追溯到圆形错误的复合和有害影响，减损了对优化求解器的隐含信任，并且特别令人担忧的是，这些网络基础设施正在被广泛用于越来越大和越来越复杂的问题。这个教师早期职业发展（CAREER）项目将寻求通过集成和建立一套成熟的算法来建立具有强大数值保证的下一代优化求解器，以低计算成本避免循环错误。预期的贡献将产生可靠的开源优化求解器，可供学术界、从业者和广大公众使用。此外，该项目还将设计和启动一个招聘和多层次的暑期研究实习计划，以提高代表性不足的学生的参与度，培养成功完成研究生学习的关键技能，并培养跨学科的学习社区。这个CAREER研究项目将开发严格的理论和计算方法，以实现现实世界的线性规划和混合整数规划的可靠，防故障的解决方案，这是一个关键的保证，超出了专门使用有限精度浮点运算的优化求解器的范围。为此，计划的活动将包括转换各种效率低下的子程序，这些子程序基于验证和/或修复优化求解器输出所需的精确有理运算，这仍然是具有数值保证的混合精度优化求解器的主要计算瓶颈。研究活动将建立在一套整数保持矩阵分解算法的基础上，这些算法将被集成到这些最先进的求解器中。此外，该项目还将探索如何重新利用以前的精确原始最优解和精确对偶可行解，以进一步增强混合精度优化求解器在数值上具有挑战性的问题上的数值保证能力。相关的活动将包括推导稀疏矩阵分解更新，利用它们来构建新的本地搜索方法，并在开源求解器上实现由此产生的算法。预计所设想的理论贡献也将具有超越优化软件开发的根本性影响。该CAREER奖由计算机和信息科学与工程（CISE）理事会计算和通信基础（CCF）部门的软件和硬件基础（SHF）计划以及土木工程部的运营工程（OE）计划共同资助，该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Mathematical programming is a systematic problem-solving approach that utilizes mathematical models and algorithms to make optimal decisions, subject to a given set of restrictions. Remarkable strides in the theory and application of this toolset over the past three decades, combined with a similarly impressive acceleration in computing capabilities, have helped proliferate the use of optimization software in science, engineering, business, and beyond. Yet, the commercial optimization solvers being utilized in practice often lack rigorous numerical guarantees which, largely unbeknownst to users, may cause them to return inconsistent results. Such outcomes can lead practitioners to draw incorrect conclusions about the problem or system being analyzed and ultimately lead to misguided and erroneous decisions. The rather unpredictable and non-negligible plausibility of these and other incorrect outcomes, which can be traced to the compounding and deleterious effects of roundoff errors, detracts from the implicit trust placed on optimization solvers, and it is specially concerning as these cyberinfrastructures are being widely employed on ever larger and more numerically complex problems. This Faculty Early Career Development (CAREER) project will seek to establish the next generation of optimization solvers with robust numerical guarantees by integrating and building on a mature suite of algorithms for avoiding roundoff errors at low computational cost. The envisioned contributions will result in reliable, open-source optimization solvers that will be made available to academics, practitioners, and the public at large. In addition, the project will design and launch a recruitment and multi-tiered summer research internship program to increase underrepresented student engagement, build critical skills for succeeding in graduate study, and foster interdisciplinary learning communities.This CAREER research project will develop rigorous theory and computational methods to enable the reliable, fail-proof solution of real-world linear programs and mixed integer programs, which is a pivotal guarantee beyond the reach of optimization solvers that work exclusively with finite-precision floating-point arithmetic. To that end, the planned activities will include transforming various inefficient subroutines based on exact rational arithmetic required to validate and/or repair optimization solver outputs, which remain the primary computational bottleneck of mixed-precision optimization solvers with numerical guarantees. The research activities will build on a suite of integer-preserving matrix factorization algorithms, which are primed to be integrated into these state-of-the-art solvers. In addition, the project will explore how to repurpose previous exact primal optimal solutions and exact dual feasible solutions to further enhance the capabilities of mixed-precision optimization solvers with numerical guarantees on numerically challenging problems. The associated activities will include deriving sparse matrix factorization updates, leveraging them to build novel local search methods, and implementing the resulting algorithms on open-source solvers. It is expected that the envisioned theoretical contributions will also have fundamental implications beyond the development of optimization software.This CAREER award is jointly funded by the Software and Hardware Foundations (SHF) Program of the Division of Computing and Communication Foundations (CCF) in the Computer and Information Science and Engineering (CISE) Directorate and the Operations Engineering (OE) Program of the Division of Civil, Mechanical and Manufacturing Innovation (CMMI) in the Engineering (ENG) Directorate.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.