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 Graczyck, 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 augmented with a diverse set of auxiliary techniques. Their performance is highly dependent on a number of interdependent individual components. Using tools from Machine Learning, we intend to study the interaction of individual decisions made in these components with the ultimate goal to improve performance. The practical implementation of resulting algorithms will involve the transfer of classic MIP techniques onto modern hardware like GPUs.

External Links

SCIP: Solving Constraint Integer Programs. https://www.scipopt.org/

Related Publications

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