Instance-wise algorithm configuration with graph neural networks

We present our submission for the configuration task of the Machine Learning for Combinatorial Optimization (ML4CO) NeurIPS 2021 competition. The configuration task is to predict a good configuration of the open-source solver SCIP to solve a mixed integer linear program (MILP) efficiently. We pose t...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2022-02
Main Authors: Romeo Valentin, Ferrari, Claudio, Scheurer, Jérémy, Amrollahi, Andisheh, Wendler, Chris, Paulus, Max B
Format: Article
Language:English
Subjects:
Algorithms
Combinatorial analysis
Competition
Configuration management
Graph neural networks
Linear programming
Machine learning
Mixed integer
Neural networks
Optimization
Solvers
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present our submission for the configuration task of the Machine Learning for Combinatorial Optimization (ML4CO) NeurIPS 2021 competition. The configuration task is to predict a good configuration of the open-source solver SCIP to solve a mixed integer linear program (MILP) efficiently. We pose this task as a supervised learning problem: First, we compile a large dataset of the solver performance for various configurations and all provided MILP instances. Second, we use this data to train a graph neural network that learns to predict a good configuration for a specific instance. The submission was tested on the three problem benchmarks of the competition and improved solver performance over the default by 12% and 35% and 8% across the hidden test instances. We ranked 3rd out of 15 on the global leaderboard and won the student leaderboard. We make our code publicly available at \url{https://github.com/RomeoV/ml4co-competition} .
ISSN:2331-8422