EF1 – Extracting dynamical Laws from Complex Data

Project

EF1-9

Adaptive Algorithms through Machine Learning: Exploiting Interactions in Integer Programming

Project Heads

Ambros Gleixner, Sebastian Pokutta

Project Members

Antonia Chmiela, Christoph Graczyk, Boro Sofranac, Christoph Spiegel

Project Duration

01.01.2021 − 31.12.2022

Located at

ZIB

Description

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.

External Links

Related Publications

  • Chmiela, A., Khalil, E., Gleixner, A., Lodi, A., Pokutta, S. (2021). Learning to Schedule Heuristics in Branch-and-Bound. Preprint available at https://arxiv.org/abs/2103.10294
  • Sofranac, B., Gleixner, A., Pokutta, S. (2020). Accelerating Domain Propagation: an Efficient GPU-Parallel Algorithm over Sparse Matrices, to appear in Proc. of IA^3 at SC20, preprint available at https://arxiv.org/abs/2009.07785
  • Gamrath, G., et al. (2020). The SCIP Optimization Suite 7.0. ZIB-Report 20-10, Zuse Institute Berlin, urn:nbn:de:0297-zib-78023

Related Pictures

Example of how to obtain a heuristic schedule from data: The data is shown on the left for three heuristics and nodes and the (optimal) schedule obtained by following the Algorithm proposed by Chmiela et al. is illustrated on the right.