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

职业：在线性和混合整数规划求解器中实现鲁棒数值保证的理论和计算进展

• 批准号: 2340527
• 负责人: Adolfo Escobedo
• 金额: $ 56.16万
• 依托单位: North Carolina State University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-08-15 至 2029-07-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2340527&HistoricalAwards=false
• 关键词: CAREER; Theoretical; Computational; Advances; Enabling

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.

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