Title: Integer programming and machine learning for computational statistics
Authors: Ulf Friedrich - Technical University of Munich (Germany) [presenting]
Jan Pablo Burgard - Trier University (Germany)
Abstract: Optimization problems are omnipresent in modern computational statistics. These typically involve computationally challenging instances and often integrality constraints on some or all of the optimization variables, e.g., to describe (binary) decisions within the model. It is therefore necessary to employ discrete optimization techniques. Methods from Integer Programming are especially relevant because powerful general-purpose solvers are available. However, based on the increasing computational power and improved processing of big data, the classical techniques to solve discrete optimization problems are often replaced by Machine Learning algorithms. While Machine Learning can generally not guarantee that a global optimum is computed, it is often several orders of magnitude faster in practical problem solving, in particular on large instances. We combine Machine Learning and Integer Programming in a single algorithm that is fast and exact. A Branch \& Bound framework adapted from Integer Programming is used to control the overall progress. By solving relaxed problems and analyzing the optimality gap, the quality of the solutions is monitored and global optimality can be proved. Simultaneously, fast Machine Learning techniques are used to generate good feasible solutions as early as possible and reduce the size of the search tree. We present a computational study that shows how this integrated approach is advantageous for large regression problems and related questions.