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

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.