This release contains the key components of the Neural Neighbourhood Selection approach, as described in the paper. The provided code implements the main components of the approach, covering data generation, training, and inference. We also provide interfaces that are left to be implemented by the user so that the code can be flexibly used in different contexts.
The following gives a brief overview of the contents; more detailed documentation is available within each file:
- 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.
To install the dependencies of this implementation, please run:
python3 -m venv /tmp/neural_lns_venv
source /tmp/neural_lns_venv/bin/activate
pip install -U pip
pip install -r requirements.txt
-
Implement the interfaces provided in
calibration.py,preprocessor.pyandsolving_utils.pyfor the timer, preprocessor / presolver and solver respectively. -
Specify valid training and validation paths in
config_train.py(i.e. <dataset_absolute_training_path> and <dataset_absolute_validation_path>). -
Train the neural neighbourhood selection model using:
cd <parent-directory-of-neural_lns> python3 -m neural_lns.train
Paper: Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs
If you use the code here please cite this paper:
@article{sonnerat2021learning,
title={Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs},
author={Sonnerat, Nicolas and Wang, Pengming and Ktena, Ira and Bartunov, Sergey and Nair, Vinod},
journal={arXiv preprint arXiv:2107.10201},
year={2021}
}
This is not an official Google product.