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

University Of California-Davis, Davis CA

Investigators

Abstract

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.