ds4dm / branch-search-trees Goto Github PK

View Code? Open in Web Editor NEW

63.0 4.0 21.0 4.87 MB

Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies (AAAI 2021)

Home Page: https://arxiv.org/abs/2002.05120

License: MIT License

Python 100.00%

aaai2021

branch-search-trees's Introduction

Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies

Giulia Zarpellon, Jason Jo, Andrea Lodi and Yoshua Bengio

This is the code for our paper Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies, accepted at AAAI 2021.

In this project, we

tackle the problem of branching variable selection in Branch-and-Bound (B&B) for Mixed-Integer Linear Programming (MILP) problems;
seek to learn branching policies that generalize across heterogeneous MILPs, regardless of the instances’ structure and formulation size.

To achieve this broader generalization scope, we

develop parameterizations of the candidate variables and of the search trees (C_t, Tree_t), and
design two DNN architectures (NoTree and TreeGate) that handle candidate sets of varying size.

Our results on MILP benchmark instances show that

incorporating a search-tree context to modulate branching aids generalization (with better test accuracy and smaller B&B trees);
the GCNN paradigm alone (Gasse et al. 2019) does not allow to generalize to new instances across different classes.

Here are our MILP evaluation results using the solver SCIP:

Below we provide links and instructions to our paper, source code, dataset, trained models and supplementary materials (SM).

Paper and supplementary materials

AAAI-21 Official version - does not include SM.
arXiv version - full version with SM.

Please use the following BibTeX to cite our paper and/or dataset:

@article{Zarpellon_Jo_Lodi_Bengio_2021, 
    title={Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies}, 
    volume={35}, 
    url={https://ojs.aaai.org/index.php/AAAI/article/view/16512}, 
    number={5}, 
    journal={Proceedings of the AAAI Conference on Artificial Intelligence}, 
    author={Zarpellon, Giulia and Jo, Jason and Lodi, Andrea and Bengio, Yoshua}, 
    year={2021}, 
    month={May}, 
    pages={3931-3939}
}

Talks and presentations

February 2-9, 2021 - Poster at the 35th AAAI Conference on Artificial Intelligence by Giulia Zarpellon. [Poster].
June 4, 2020 - Presentation at the SCIP Online Workshop 2020 by Giulia Zarpellon. [Youtube video] | [Slides].

Installation and dependencies

We use SCIP 6.0.1 and we use a customized version of PySCIPOpt, which we provide here:
https://github.com/ds4dm/PySCIPOpt/tree/branch-search-trees.

Once SCIP 6.0.1 has been installed, our branch-search-trees customized version of PySCIPOpt can be installed via pip:

pip install git+https://github.com/ds4dm/PySCIPOpt.git@branch-search-trees

All other requirements are in requirements.txt.

Dataset

The branch-search-trees dataset is hosted at the Open Science Framework (OSF):
https://osf.io/uvg5f/.

Our dataset consists of the following files:

train.h5: a H5 file containing all the train data.
val.h5: a H5 file containing all the validation data.
test.h5: a H5 containing all the test data.
train_instances/: a directory containing the 19 train MILP instances.
test_instances/: a directory containing 8 test MILP instances.
cutoff_dict.pkl: a pickle file containing all the cutoff values for the instances.
instance_dict.pkl: a pickle file containing the names of instances and if they belong to the train or test split.

How to create the dataset

We share how we produced the above dataset. Note that exact replication of our dataset collection may be dependent on the machine hardware. Nonetheless, we provide the code for transparency and in case others want to produce their own data.

Data collection from SCIP

Specify system-specific paths in collect.py:

paths = {
    'MYSYSTEM': {
        'out_dir': '',          # path to output directory
        'instances_dir': '',    # path to MILP instances
        'cutoff_dict': '',      # path to pickled dictionary containing cutoff values
    },
}

Data collection runs instance-wise, as:

python collect.py -n INSTANCE_NAME \
                  -s SCIP_SEED \
                  -k K_RANDOM_PAR \
                  --setting SCIP_SETTING \
                  --system MYSYSTEM \
                  -v

Note that INSTANCE_NAME contains file extension, but not path to files (e.g., air05.mps.gz). All MILP instances should be contained in paths['MYSYSTEM']['instances_dir]. For each roll-out a pickle file is saved in paths['MYSYSTEM']['out_dir].

HDF5 creation

Once we have all the SCIP collect files, we use utilities/convert_multi_instance_pickle_to_hdf5.py to convert all the collect pickle files into a single H5 file. We refer to the main paper for the exact train/val/test split and leave to the user to partition the collected files in the appropriate manner.

Note on PySCIPOpt states

Our custom SCIP functions and input parameterizations are defined in src/pyscipopt/scip.pyx of the PySCIPOpt branch branch-search-trees (see link above).
In particular, the parameterization of the search tree Tree_t is given by concatenation of getNodeState and getMIPState, while the candidate variables representation C_t is defined in getCandsState.

Experiments

Imitation Learning (IL)

To train a policy using our optimization settings:


python train_test_IL.py  --policy_type POLICY_TYPE \
                         --hidden_size HIDDEN \
                         --depth DEPTH \
                         --train_h5_path PATH_TO_TRAIN_H5 \
                         --val_h5_path PATH_TO_VAL_H5 \
                         --test_h5_path PATH_TO_TEST_H5 \
                         --out_dir OUT_DIR_PATH \
                         --use_gpu \
                         --lr LR

For the NoTree policies, depth is not a relevant hyper-parameter, so you can use DEPTH=1.

To evaluate a trained policy:


python evaluate_IL.py --checkpoint PATH_TO_PYTORCH_CHECKPOINT \
                      --cutoff_dict PATH_TO_CUTOFF_DICT \
                      --instances_dir PATH_TO_RELEVANT_INSTANCE_DIR \
                      --out_dir PATH_TO_SAVE_SCIP_EVAL_DATA \
                      --name INSTANCE_NAME \
                      --seed SCIP_SEED

In the trained-models/ directory we provide the trained NoTree and TreeGate models and their SCIP evaluations from our paper.
Best parameters and results from the GCNN models obtained by running the code of Gasse at al. are also included.

SCIP evaluations

Similarly to what is done in data collection, specify system-specific paths in evaluate_SCIP.py:

paths = {
    'MYSYSTEM': {
        'out_dir': '',          # path to output directory
        'instances_dir': '',    # path to MILP instances
        'cutoff_dict': '',      # path to pickled dictionary containing cutoff values
    },
}

Then specify instance, seed, SCIP branching policy (e.g., relpscost, pscost, random) and settings as:

python evaluate_SCIP.py -n INSTANCE_NAME \
                        -s SCIP_SEED \
                        -p SCIP_POLICY 
                        --setting SCIP_SETTING 
                        --system MYSTSTEM

Questions?

Please feel free to submit a GitHub issue if you have any questions or find any bugs. We do not guarantee any support, but will do our best if we can help.

branch-search-trees's People

Contributors

Stargazers

Watchers

branch-search-trees's Issues

[Feature request] Recurrent GatingNet

While the dataset we constructed is collected in an inherently sequential manner (it is a rollout of the SCIP default branching scheme), we randomly shuffle all the data and train as if all the datapoints are independent and identically distributed (iid). The motivating question is how accurate is this iid assumption?

There are two sides of the argument:
(1) Pro-iid camp: The hand-crafted features are themselves temporal and we are effectively in a Markovian setting.

(2) Anti-iid camp: While the features are themselves temporal, they are not temporal enough. There's still lots of temporal information we are failing to capture, which ultimately hinders generalization performance.

Currently our GatingNet is a feedforward multi-layer perceptron (MLP). The feature request is to modify the GatingNet to be a recurrent neural network. Instead of breaking sequentiality of our collected data, we preserve sequentiality and train in episodes or collected SCIP rollouts. This will require coding up new data-loaders and padding the sequences to allow for batch-wise training of episodes. Backpropagation through time (BPTT) may also need to be employed as for some of the more difficult instances, the rollouts can easily get into the thousand time-step range.

We measure if using a recurrent GatingNet improves generalization performance, both the (tangential but "standard" ML loss and accuracy metrics) and the MILP solver evaluation metrics.

Error about collect.py file

Dear professor,

Sorry for bothering.

When I run the collect.py file. I got this error,

AttributeError: 'pyscipopt.scip.Model' object has no attribute 'getNNodesLeft'

This is my 'paths' setting

paths = {
'MYSYSTEM': {
'out_dir': 'new_dataset',
'instances_dir': 'branch-search-trees-dataset/train_instances/',
'cutoff_dict': 'branch-search-trees-dataset/cutoff_dict.pkl',
},
}

This is my run command
python collect.py -n air05.mps.gz \
-s 0 \
-k 10 \
--setting sandbox \
--system MYSYSTEM \
-v

The version of PySCIPOpt is 1.4.9, which is the same as in requirements.txt and I checked the functions inside the model through the dir(model) method, and did not find functions such as getNNodesLeft, getCandsState, getNodeState, and getMIPState.

Could you help me? How do you think about this error? Thank you very much, professor.

Sincerely.

Getting Scip-status as infeasible

Hi,
I ran the evaluate_scip.py with 'nu25-pr12.mps.gz' instance( and a few others such as mine-166-5.mps.gz), it shows status ( scip-getStatus() as infeasible).

It becomes feasible if I comment this "m.setObjlimit(cutoff_value)".

Can you please help with this.

Can we generate instances using ecole?

Dear authors,

I know that the instances you used are from some standard library, but I am wondering if there is a way to generate some synthetic instances by ecole (the platform also from your group)? Is it possible? I have used ecole for some time. For the candidate node embedding I guess we can use the node_observation.column_features (maybe plus some post-processing transform to get what you designed in paper), but I could not find a way to find a cutoff value for a MILP problem in ecole. Is the cutoff value necessary here?

Thanks anyway for this interesting work and I like it very much!

Doubt in running evaluate_IL.py

Hi,
I was trying to use the model provided in trained-models.

I had a few doubts:
for instance:

for map18 for seeds 0 1 2 3 4
I am getting the following number of nodes:
653, 747, 739, 519, 681

However, the paper reports shifted geometric mean of ~575.

Could the results vary too much ?

Do you compare the solving time between default SCIP policies and learned policies ?

Great job! Very inspiring.

However, I think there is a lack of comparison of solving time between different methods in the same instances.
Although the paper reports the number of nodes explored by learned and SCIP policies, the number of nodes and solving time are not exactly equivalent. Neural network policies maybe run faster than default SCIP policies with the same number of explored nodes.

A lot of people pay attention to ML4CO because of its potential to speed up solving MILP problems. It would be better and more intuitive that there is a solving time comparison, just like Exact Combinatorial Optimization with Graph Convolutional Neural Networks, Gasse et al.

Doubt in version of pyscipopt

Hi,
I know your customized version of pyscipopt must be installed to run the code. I have a question. Your customized version of pyscipopt is based on version 1.4.9. However, Pyscipopt has been updated to version 4.0.0, involving many added, removed or fixed functionality. If I want to use some new added function which exists in higher version of pyscipopt such as model.redirectOutput(), what should I do?
Thank you in advance! Looking forward to your reply!

Reproduction issues

Hello! We have been reproducing the results of your insightful paper entilted " Parameterizing Branch-and-Bound Search Trees to
Learn Branching Policies " and encountered some issues. First of all, we appreciate that you publish your code and data in the repo.
And we utilize the data from the repo and the hyperparameters from the model file trying to reproduce retrain the model. The val/test
acc of NT and val acc of TG are similar to the results reported in the paper. But, the test acc of TG is 74.17%.
We are looking forward to discussing with you.
ps:

our model hyperparam:

    Namespace(depth=5, dim_reduce_factor=2, dropout=0.0, eval_batchsize=500, hidden_size=64, infimum=8, lr=0.01, lr_decay_factor=0.1, lr_decay_schedule=[20, 30], momentum=0.9, norm='none', num_epochs=40, opt='adam', out_dir='trained-models/TreeGatePolicy_hidden64_depth5_lr0.01', policy_type='TreeGatePolicy', seed=0, test_h5_path='data/test.h5', top_k=[2, 3, 5, 10], train_batchsize=32, train_h5_path='data/train.h5', use_gpu=True, val_h5_path='data/val.h5', weight_decay=1e-05)

model hyperparam from repo:

    Namespace(depth=5, dim_reduce_factor=2, dropout=0.0, eval_batchsize=500, hidden_size=64, infimum=8, lr=0.01, lr_decay_factor=0.1, lr_decay_schedule=[20, 30], momentum=0.9, norm='none', num_epochs=40, opt='adam', out_dir='trained-models/TreeGatePolicy_hidden64_depth5_lr0.01', policy_type='TreeGatePolicy', seed=0, test_h5_path='data/test.h5', top_k=[2, 3, 5, 10], train_batchsize=32, train_h5_path='data/train.h5', use_gpu=True, val_h5_path='data/val.h5', weight_decay=1e-05)

Best,
Zhi

ILEvalBrancher and SCIPCollectBrancher

Hello! I have a question. In the file brancher.py, maybe the code self.branchexec_count += 1 in line 56 should be placed after line 59? Otherwise, there is bias during the test phase because the same code in class SCIPCollectBrancher in line 161 is placed after line 154.