Branch to Learn

---

Learning the optimal branching variable in Mixed Integer Linear Programming branch-and-bound algorithms with graph convolutional neural networks and multi-layer perceptrons. This repository contains the source code for my master's thesis Ablating a Graph convolutional Network for Branching in Mixed-Integer Linear Programming. The project uses Ecole by DS4DM.

About

This thesis is a continued exploration and development of ideas from two articles:

Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, Andrea Lodi Exact Combinatorial Optimization with Graph Convolutional Neural Networks (2019).

Prateek Gupta, Maxime Gasse, Elias B. Khalil, M. Pawan Kumar, Andrea Lodi, Yoshua Bengio: Hybrid Models for Learning to Branch (2020)

And implements variations of these ideas in the freamework Ecole, which is found in the article:

Antoine Prouvost, Justin Dumouchelle, L. Scavuzzo, Maxime Gasse, D. Chételat, A. Lodi: Ecole: A Gym-like Library for Machine Learning in Combinatorial Optimization Solvers

This is the code for my master's thesis for a Master of Science in Engineering Cybernetics at the Norwegian University of Science and Technology. The title of the project is "Ablating a Graph Neural Network for Branching in Mixed-Integer Linear Programming". Feel free to contact me about any and all details of this project.

Installation

Installation instructions are given in INSTALL.md

How to run it?

To recreate results, choose a problem, model and device. Following is an example of how to do this.

First, set the variables, for example:

PROBLEM=setcover
MODEL=mlp2
DEVICE=0

Generate Dataset

python branch2learn/01_generate_data.py -p $PROBLEM

Train model

python branch2learn/02_train.py -p $PROBLEM -m $MODEL -g $DEVICE

Test model performance

python branch2learn/03_test.py -p $PROBLEM -m $MODEL -g $DEVICE

Evaluate models

python branch2learn/04_evaluate.py -p $PROBLEM -m $MODEL -g $DEVICE

Evaluate default policies

python branch2learn/05_evaluate_standard.py -p $PROBLEM -m fsb

Or, you can run all experiments with one bash script:

Run all experiments

./scripts/run.sh

Citation

Please cite the three original papers as well as my thesis if you use this code in your work, and feel free to contact @Sandbergo about anything related to the project.

Questions / Bugs

Please feel free to submit a Github issue if you have any questions or find any bugs.