This directory is the official implementation for our NeurIPS 2023 paper Learning to Configure Separators in Branch-and-Cut. This README file provides instructions on environment setup, data collection, restricted configuration space construction, model training and testing.
You may find this project at: Project Website, arXiv, OpenReview.
@inproceedings{li2023learning,
title={Learning to Configure Separators in Branch-and-Cut},
author={Sirui Li and Wenbin Ouyang and Max B. Paulus and Cathy Wu},
booktitle={Thirty-seventh Conference on Neural Information Processing Systems},
year={2023},
url={https://openreview.net/forum?id=gf5xJVQS5p}
}
Our implementation uses python 3.8.13 and Pytorch 1.9.0. The other package dependencies are listed in requirement.txt
and can be installed with the following command:
pip install -r requirements.txt
Beside the listed python packages, we also use a custom version of the SCIP solver (v7.0.2) and the PySCIPOpt interface (v3.3.0), kindly provided by the authors of [1], that allows activating and deactivating separators at intermediate separation rounds during each solve (see Appendix A.6.3 for details). We are informed that the authors of [1] will make the code publicly available soon. The SCIP and PySCIPOpt plug-in follows a similar design to the one found at https://github.com/avrech/learning2cut, which is publicly available.
[1] Paulus, Max B., et al. "Learning to cut by looking ahead: Cutting plane selection via imitation learning." International conference on machine learning. PMLR, 2022.
We provide code for data generation in the ./data_generation
folder for Tang et al. [2] and Ecole [3] benchmarks. We also provide download instructions and data filtering code for real-world large-scale benchmarks (NNV, MIPLIB, Load Balancing). The collected data are stored in the ./data
folder.
One can generate the data simply by:
cd data_generation
python generate_tang.py
python generate_ecole.py
The default save directory is ./data
, and can be changed by specifying the --path_to_data_dir
argument of two programs. One can refer to [2] and [3] for changing MILP parameters. We do not filter instances from Tange et al. and Ecole.
- An example Packing instance from Tang et al. can be found in
./example/example_packing_instance.mps
. - We include the size of the instances in the suffix. For example, if the save directory is
./data
, packing instances will be saved in./data/packing-60-60
[2] Tang, Yunhao, Shipra Agrawal, and Yuri Faenza. "Reinforcement learning for integer programming: Learning to cut." International conference on machine learning. PMLR, 2020. [3] Prouvost, Antoine, et al. "Ecole: A gym-like library for machine learning in combinatorial optimization solvers." arXiv preprint arXiv:2011.06069 (2020).
The NN Verification dataset can be downloaded at https://github.com/deepmind/deepmind-research/tree/master/neural_mip_solving. The MIPLIB dataset can be downloaded at https://miplib.zib.de/download.html. The Load Balancing dataset can be downloaded at https://github.com/ds4dm/ml4co-competition/blob/main/START.md.
We filter out some of the instances from the real-world benchmarks with the following code (see Appendix A.6.5 for details):
cd data_generation
python data_filter.py --instances [MILP class to be filtered] \
--path_to_raw_data_dir [directory of the downloaded data] \
--path_to_data_dir [save directory] \
--time_limit [time limit] \
--gap_limit [gap limit] \
--index_end [total number of the instances to consider]
Specifically, we can run the following commands to filter NNV, MIPLIB, and Load Balancing, assuming the raw data is saved in the ./data/raw/{instances}
directory:
cd data_generation
python data_filter.py --instances nnv --path_to_raw_data_dir ../data/raw --path_to_data_dir ../data --time_limit 120 --index_end 1800
python data_filter.py --instances load_balancing --path_to_raw_data_dir ../data/raw --path_to_data_dir ../data --time_limit 300 --gap_limit 0.1 --index_end 1600
python data_filter.py --instances miplib --path_to_raw_data_dir ../data/raw --path_to_data_dir ../data --time_limit 300 --gap_limit 0.1 --index_end 1065
The dataset after filtering will be stored in the ./data
folder.
After generating or filtering the problem instances, one can separate the datasets into train, validation and test sets. The default saving directories are ./data/{instance}_train
, ./data/{instance}_val
and ./data/{instance}_test
. And the default ratio for these three sets is 8:1:1.
For example, after generating 1000 packing instances, copy and paste the first 800 instances from ./data/packing-60-60
to ./data/packing-60-60_train
, 801st to 900th instances to ./data/packing-60-60_val
and the last 100 instances to./data/packing-60-60_test
.
For the hetergeneous dataset MIPLIB, to ensure the distributions of the train, validation and test sets are roughly the same, a random shuffle of the instances are needed. Assume after filtering, ./data/miplib/sequence.npy
to indicate the sequence of the instances after shuffling.
We provide instructions on constructing the restricted configuration space, following Alg.1 in Appendix A.3.
We first use random search to find a good instance-agnostic configuration, which we later use to construct the "Near Best Random" initial configuration subset (See Appendix A.3).
cd restricted_space_generation
python find_best_ins_agnostic.py --instances [the MILP class] \
--path_to_data_dir [directory of the data] \
--gap_limit [gap limit]
- For example, one can run the following code for the Packing MILP class in Tang et al.:
cd restricted_space_generation
python find_best_ins_agnostic.py --instances packing-60-60 --path_to_data_dir ../data --gap_limit 0.0
The result will be stored as a best_ins_agnostic.npy
file in the ./restricted_space/{instances}
folder.
We apply the "Near Zero" and "Near Best Random" strategies as described in Appendix A.3.1 to construct the large initial configuration subset for later constructing the restricted space.
cd restricted_space_generation
python explore_subspace.py --instances [the MILP class] \
--path_to_data_dir [directory of the data] \
--path_to_ins_agnst [directory of the best instance-agnostic configuration] \
--mode [the strategy to apply] \
- For example, one can run the following code for applying the "Near Zero" strategy to the Packing MILP class in Tang et al.:
cd restricted_space_generation
python explore_subspace.py --instances packing-60-60 --path_to_data_dir ../data --path_to_ins_agnst ../restricted_space/ --mode near_zero
- and the following code for applying "Near Best Random":
cd restricted_space_generation
python explore_subspace.py --instances packing-60-60 --path_to_data_dir ../data --path_to_ins_agnst ../restricted_space/ --mode near_mask
The results will be stored in the ./restricted_space/{instances}/{strategy_name}
folder.
We then run the following code to combine the above sampled configurations into a single configuration subset
cd restricted_space_generation
python get_actions.py --instances [the MILP class] \
--path_to_space_dir [directory of the sampled configurations]
The code will generate two .npy
files: action_space.npy
contains all the configurations in this set action_scores.npy
includes the relative time improvement of each configuration in
- For example, one can run the following code to abtain the configuration subset
$S$ for Packing MILP class.
cd restricted_space_generation
python get_actions.py --instances packing-60-60 --path_to_space_dir ../restricted_space/
We construct the restricted space ./restricted_space/restricted_space_generation.ipynb
which analyzes action_space.npy
and action_scores.npy
. The MILP class can be specified by changing the instances
variable in the first cell.
By adjusting our_size
(candidate size of Bs
(candidate threshold
Finally, we run the last cell to store the restricted space ./restricted_space/{instances}/restricted_actions_space.npy
, and the instance-agonstic ERM configuration (one of ours heuristic variants) will be stored to ./restricted_space/{instances}/inst_agnostic_action.npy
.
- Example restricted action space could be found in
./example/restricted_space/{instances}/restricted_actions_space.npy
We provide instructions for training the models for
For training the model
python train_k1.py --instances [the MILP class]
The default directory of the restricted action space is ./restricted_space/{instance}/restricted_actions_space.npy
. One can change that by modifying the --actiondir
and the --actions_name
. The default directory for saving the model and ./model/{instances}_k1
. One can change the save directory by modifying the --savedir
argument.
For training the model
python train_k2.py --instances [the MILP class] \
--model_0_path [path to the model of k=1] \
--Z_0_path [Matrix Z for k=1] \
--step_k2 [the value of n_2]
- For example, one can run the following code to train the model
$\tilde{f}^{2}$ at$k = 2$ for the Packing MILP class in Tang et al.:
python train_k2.py --instances packing-60-60 --model_0_path ./model/packing-60-60_k1/model-42 --Z_0_path ./model/packing-60-60_k1/Z-42 --step_k2 5
The default directory for saving the model and ./model/{instances}_k2
. One can change the save directory by modifying the --savedir
argument.
- Example pretrained models
$\tilde{f}^{1}$ ,$\tilde{f}^{2}$ and the associated$Z^1, Z^2$ matrices can be found at:./example/model/{instances}/model_k1
,./example/model/{instances}/model_k2
,./example/model/{instances}/Z_k1
, and./example/model/{instances}/Z_k2
.
To test the models
python test_k2.py --instances [the MILP class] \
--model_0_path [path the model of k=1] \
--Z_0_path [Matrix Z for k=1] \
--model_path [path the model of k=2] \
--Z_path [Matrix Z for k=2] \
--step_k2 [the value of n_2]
- For example, one can run the following code to test the models for the Packing MILP class in Tang et al.:
python test_k2.py --instances packing-60-60 --model_0_path ./model/packing-60-60_k1/model-42 --Z_0_path ./model/packing-60-60_k1/Z-42 --model_path ./model/packing-60-60_k2/model-42 --Z_path ./model/packing-60-60_k2/Z-42 --step_k2 5
The testing results will be printed to the console.