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

Mixed-integer (linear and nonlinear) optimization is a discipline of mathematical optimization that is concerned with nite-dimensional, non-convex optimization problems that in- clude discrete decision variables such as those that model \yes/no" decisions. Problems of this type arise in all areas of industry, in the guise of operations research. Algorithms for mixed-integer opti- mization build upon convex optimization technology by relaxation, approximation, convexication, and decomposition techniques. The trend to ever increasing problem sizes due to the availability of Big Data has created new challenges that need to be addressed by a next generation of algorithms. In this project, we focus on convexication, in particular the eective and ecient generation of cutting planes. In the linear case, we build upon a powerful abstraction of the convexication process, the notion of cut-generating functions (cgf), which can explain the major cutting plane procedures in use in today's solvers. In this abstraction, computing a cutting plane is considered ecient, because each of its coecients is obtained by just evaluating the cgf on problem data; rather than by running an algorithm. Prompted by recent research that has led to more and more complicated cgfs, and by the goal of developing multi-row and multi-cut cutting plane systems, we open up this abstraction. We investigate and develop classes of cgf that can be eciently represented and evaluated and eciently selected for greatest eectiveness on a given problem. For single-row cutting-plane systems like the traditional Gomory mixed-integer cut, ecient evaluation can be achieved by restricting to a family of piecewise linear cgf with a small number of breakpoints. We propose to compute the space of all extreme continuous piecewise linear cgf of the Gomory{Johnson model with at most 20 breakpoints and at most 4 dierent slopes. This is a space consisting of semialgebraic cells, parametrizing subadditive piecewise linear functions, glued at the boundary where degeneration occurs. The computation of each cell requires the proof of a theorem; we develop automated theorem proving technology for this, based on metaprogramming and semialgebraic computations. By theoretical and computational techniques, we investigate the local and global structure of this space; on this foundation we then develop optimization algorithms for the ecient selection of eective cgfs for a given problem. For novel multi-row cutting-plane systems, it is crucial to be able to compress a cgf so that it can be represented in a small amount of space. We will study ways of representing cgfs in a neural-network architecture. Under the new architecture input, we will prove new theorems for determining extremality. Further, we will use derivative-free mixed integer optimization to create optimally compact descriptions of these functions and verify their improved evaluation eciency computationally. Equally important as strength of cutting planes is the diversity of cutting planes. Within a solver, many cutting planes will be applied and determining which cutting planes to use in conjunction can have enormous impact on their eectiveness. We propose to study diversity of cut- generating functions in the context of our model through the means of several dierent metrics. This will include theorems regarding the strongest k-cuts to use in conjunction along with algorithms to measure the diversity of a set of input functions. Assessing diversity at the cut-generating function level will allow eectively diverse cuts to be utilized without added overhead of detecting diversity online.