An implementation of Neural Diving

Overview

This project implement Neural Diving, a model from DeepMind to solve large scale Mixed Integer Programming Problem. Neural Diving use a Graph Neural Network to generate partial variable assignment and create sub-problem, the remaining variable can be assign by using SCIP. The code is inspired by Large Neighborhood Search Algorithm from DeepMind. To install SCIP, please follow this installation guide.

Overview of the component

• calibration.py: Abstract timer for MIP solving.
• config_train.py: Configuration file for training parameters.
• data_utils.py: Utility functions for feature extraction.
• layer_norm.py: Model layer normalisation and dropout utilities.
• light_gnn.py: The GNN model used for training.
• local_branching_data_generation.py: Library with functions required to generate imitation data.
• local_branching_expert.py: Expert for Neural Large Neighbourhood Search based on local branching.
• mip_utils.py: MIP utility functions.
• preprocessor.py: Abstract APIs for MIP preprocessor.
• sampling.py: Sampling strategies for Neural LNS.
• solution_data.py: SolutionData classes used to log solution process.
• solvers.py: Neural diving and neural neighbourhood selection implementations.
• solving_utils.py: Common utilities for solvers.py.
• train.py: Training script for neural neighbourhood selection model.
• data: Directory with example tfrecord file to run training. The example dataset is derivative of open-sourced NN Verification Dataset.

Installation

To install the dependencies of this implementation, please run:

pip install -U pip
pip install -r requirements.txt

Usage

1. Implement the interfaces provided in calibration.py, preprocessor.py and solving_utils.py for the timer, preprocessor / presolver and solver respectively.

2. Specify valid training and validation paths in config_train.py (i.e. <dataset_absolute_training_path> and <dataset_absolute_validation_path>).

3. Train the neural neighbourhood selection model using:

   cd <parent-directory-of-neural_diving>
   python3 -m neural_diving.train
   

Reference

Paper: Solving Mixed Integer Programs Using Neural Networks Reference Code: neural_lns

Disclaimer