Adaptive Algorithms Through Machine Learning: Exploiting Interactions in Integer Programming completed

Modern Mixed Integer Linear Programming solvers are among the most complex algorithms implemented in software today. They commonly rely on a Branch-and-Cut approach: the MILP problem is first relaxed to a Linear Program by dropping integrality requirements. One then iteratively adds additional constraints to the feasible region of the problem that are violated by the current solution of the relaxation but valid for the original problem. These constraints commonly can take the form of simple bounds on non-integral components of the current solution. Both constraints need to be explored, as either could be violated by any actual solution to the original MILP, motivating the Branch part of Branch-and-Cut. The other form of constraints one can add are cutting planes, that is inequalities resulting from the solution of the current iteration of LP relaxation, which are still violated by the current solution of the relaxation, but are guaranteed to be fulfilled by any actual solution to the original MILP. On top of these two basic components, most MIP solvers additionally employ a number of interdependent individual components to improve performance. The most notable of these components are Primal heuristics, targeted at quickly finding good feasible solutions to the problem. The performance of any such solver is therefore highly dependent on individual decisions made at each iteration, that is for the choice of cuts to add, variable to branch on or heuristic to execute. Over the last decade there has been an explosion of applications in which Machine Learning methods, and in particular Deep Neural Networks, have displayed an almost uncanny ability to learn decision-making in highly complex and dynamic environments. As a result, there has been an increasing yet still nascent interest in using Artificial Intelligence as a tool for tackling the degrees of freedom in many of the algorithmic choices made by MILP solvers. Using tools from Machine Learning, this project is therefore aimed at studying the interaction of individual decisions made in the components of a MIP solver with the ultimate goal to improve performance. The practical implementation of resulting algorithms will also involve the transfer of classic MIP techniques onto modern hardware like GPUs. In this project, algorithmic and hardware paradigms from the field of machine learning have been exploited to accelerate critical components of solvers for mixed integer programming, not merely for homogeneous test sets as is typical in the community of machine learning, but over heterogeneous test sets for MIP benchmarking. Our GPU-parallel domain propagation is around 10x to 20x faster than previously available sequential implementations, and up to 180x on favorably-large instances. Our scheduling algorithms for primal heuristics manage to reduce the average primal integral by 49% on challenging sets of instances.