Implementation of our NeurIPS 2021 paper "A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs".

Overview

PPO-BiHyb

This is the official implementation of our NeurIPS 2021 paper "A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs".

A Brief introduction

In this paper, we propose a general deep learning pipeline for combinatorial optimization problems on graphs. The neural network is learned with Proximal Policy Optimization (PPO), under our Bi-Level Hybrid optimization pipeline. Thus our method is called PPO-BiHyb. This section is aimed for a brief summary, and we recommend referring to our paper if you do not want to miss any details.

The family of existing machine learning for combinatorial optimization methods follow the following single-level pipeline: single-level optimization and the neural network is designed to lean the mapping from the input graph G to the decision variable X. It brings challenges like the sparse reward issue in RL training, and it also makes the model design non-trivial to ensure that it has enough model capacity to learn such a mapping.

In contrast, in this paper, we propose a bi-level optimization formulation: bi-level optimization where we introduce the optimized graph G'. The upper-level problem is to optimize G', and we design a PPO-based agent for this task; the lower-level optimization is to solve the optimization problem with G', and we resort to existing heuristic algorithms for this task.

The overview of our pipeline is summarized as follows overview

And Here is our implementation of the proposed framework on 3 problems: implement-on-3-problems

  • DAG scheduling problem models the computer resource scheduling problem in data centers, where the computer jobs are represented by Directed Acyclic Graphs (DAGs) and our aim is to minimize the makespan time to finish all jobs as soon as possible. This optimization problem is NP-hard.
  • Graph Edit Distance (GED) problem is a popular graph distance metric, and it is inherently an NP-hard combinatorial optimization problem whose aim is to minimize the graph edit cost between two graphs.
  • Hamiltonian Cycle Problem (HCP) arises from the famous 7 bridges problem by Euler: given a graph, decide whether exist a valid Hamiltonian cycle in this graph (i.e. a path that travels all nodes without visiting a node twice). This decision problem is NP-complete.

Experiment Results

DAG scheduling (objective & relative: smaller is better)

TPC-H-50 (#nodes=467.2) TPC-H-100 (#nodes=929.8) TPC-H-150 (#nodes=1384.5)
objective relative objective relative objective relative
shortest job first 12818 30.5% 19503 15.3% 27409 12.2%
tetris scheduling 12113 23.3% 18291 8.1% 25325 3.7%
critical path 9821 0.0% 16914 0.0% 24429 0.0%
PPO-Single 10578 7.7% 17282 2.2% 24822 1.6%
Random-BiHyb 9270 -5.6% 15580 -7.9% 22930 -6.1%
PPO-BiHyb (ours) 8906 -9.3% 15193 -10.2% 22371 -8.4%

GED (objective & relative: smaller is better)

AIDS-20/30 (#nodes=22.6) AIDS-30/50 (#nodes=37.9) AIDS-50+ (#nodes=59.6)
objective relative objective relative objective relative
Hungarian 72.9 94.9% 153.4 117.9% 225.6 121.4%
RRWM 72.1 92.8% 139.8 98.6% 214.6 110.6%
Hungarian-Search 44.6 19.3% 103.9 47.6% 143.8 41.1%
IPFP 37.4 0.0% 70.4 0.0% 101.9 0.0%
PPO-Single 56.5 51.1% 110.0 56.3% 183.9 80.5%
Random-BiHyb 33.1 -11.5% 66.0 -6.3% 82.4 -19.1%
PPO-BiHyb (ours) 29.1 -22.2% 61.1 -13.2% 77.0 -24.4%

HCP (TSP objective: smaller is better, found cycles: larger is better)

FHCP-500/600 (#nodes=535.1)
TSP objective found cycles
Nearest Neighbor 79.6 0%
Farthest Insertion 133.0 0%
LKH3-fast 13.8 0%
LKH3-accu 6.3 20%
PPO-Single 9.5 0%
Random-BiHyb 10.0 0%
PPO-BiHyb (ours) 6.7 25%

Environment set up

This code is developed and tested on Ubuntu 16.04 with Python 3.6.9, Pytorch 1.7.1, CUDA 10.1.

Install required pacakges:

export TORCH=1.7.0
export CUDA=cu101
pip install torch==1.7.1+${CUDA} torchvision==0.8.2+${CUDA} torchaudio===0.7.2 -f https://download.pytorch.org/whl/torch_stable.html
pip install --no-index --upgrade torch-scatter -f https://pytorch-geometric.com/whl/torch-${TORCH}+${CUDA}.html
pip install --no-index --upgrade torch-sparse -f https://pytorch-geometric.com/whl/torch-${TORCH}+${CUDA}.html
pip install --no-index --upgrade torch-spline-conv -f https://pytorch-geometric.com/whl/torch-${TORCH}+${CUDA}.html
pip install --upgrade torch-geometric
pip install tensorboard
pip install networkx==2.2
pip install ortools
pip install texttable
pip install tsplib95
pip install cython

Install SVN which is required when retriving the GED dataset:

sudo apt install subversion

Compile the A-star code which is required by the GED problem:

python3 setup.py build_ext --inplace

Install LKH-3 which is required by the HCP experiment:

wget http://webhotel4.ruc.dk/~keld/research/LKH-3/LKH-3.0.6.tgz
tar xvfz LKH-3.0.6.tgz
cd LKH-3.0.6
make

And you should find an executable at ./LKH-3.0.6/LKH, which will be called by our code.

Run Experiments

We provide the implementation of PPO-BiHyb and the single-level RL baseline PPO-Single used in our paper. To run evaluation from a pretrained model, replace train by eval in the following commands.

DAG Scheduling

PPO-BiHyb:

python dag_ppo_bihyb_train.py --config ppo_bihyb_dag.yaml

PPO-Single:

python dag_ppo_single_train.py --config ppo_single_dag.yaml

To test different problem sizes, please modify this entry in the yaml file: num_init_dags: 50 (to reproduce the results in our paper, please set 50/100/150)

Graph Edit Distance (GED)

PPO-BiHyb:

python ged_ppo_bihyb_train.py --config ppo_bihyb_ged.yaml

PPO-Single:

python ged_ppo_single_train.py --config ppo_single_ged.yaml

To test different problem sizes, please modify this entry in the yaml file: dataset: AIDS-20-30 (to reproduce the results in our paper, please set AIDS-20-30/AIDS-30-50/AIDS-50-100)

Hamiltonian Cycle Problem (HCP)

PPO-BiHyb:

python hcp_ppo_bihyb_train.py --config ppo_bihyb_hcp.yaml

PPO-Single:

python hcp_ppo_single_train.py --config ppo_single_hcp.yaml

Some Remarks

The yaml configs are set for the smallest sized problems by default. For PPO-Single, you may need to adjust the max_timesteps config for larger-sized problems to ensures that the RL agent can predict a valid solution.

Pretrained models

We provide pretrained models for PPO-BiHyb on these three problems, which are stored in ./pretrained. To use your own parameters, please set the test_model_weight configuration in the yaml file.

Citation and Credits

If you find our paper/code useful in your research, please citing

@inproceedings{wang2021bilevel,
    title={A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs}, 
    author={Runzhong Wang and Zhigang Hua and Gan Liu and Jiayi Zhang and Junchi Yan and Feng Qi and Shuang Yang and Jun Zhou and Xiaokang Yang},
    year={2021},
    booktitle={NeurIPS}
}

And we would like to give credits to the following online resources and thank their great work:

Owner
[email protected]
Thinklab at Shanghai Jiao Tong University, led by Prof. Junchi Yan.
<a href=[email protected]">
The implementation of "Optimizing Shoulder to Shoulder: A Coordinated Sub-Band Fusion Model for Real-Time Full-Band Speech Enhancement"

SF-Net for fullband SE This is the repo of the manuscript "Optimizing Shoulder to Shoulder: A Coordinated Sub-Band Fusion Model for Real-Time Full-Ban

Guochen Yu 36 Dec 02, 2022
Over9000 optimizer

Optimizers and tests Every result is avg of 20 runs. Dataset LR Schedule Imagenette size 128, 5 epoch Imagewoof size 128, 5 epoch Adam - baseline OneC

Mikhail Grankin 405 Nov 27, 2022
Creating predictive checklists from data using integer programming.

Learning Optimal Predictive Checklists A Python package to learn simple predictive checklists from data subject to customizable constraints. For more

Healthy ML 5 Apr 19, 2022
Planner_backend - Academic planner application designed for students and counselors.

Planner (backend) Academic planner application designed for students and advisors.

2 Dec 31, 2021
Finetune alexnet with tensorflow - Code for finetuning AlexNet in TensorFlow >= 1.2rc0

Finetune AlexNet with Tensorflow Update 15.06.2016 I revised the entire code base to work with the new input pipeline coming with TensorFlow = versio

Frederik Kratzert 766 Jan 04, 2023
Implementation of "StrengthNet: Deep Learning-based Emotion Strength Assessment for Emotional Speech Synthesis"

StrengthNet Implementation of "StrengthNet: Deep Learning-based Emotion Strength Assessment for Emotional Speech Synthesis" https://arxiv.org/abs/2110

RuiLiu 65 Dec 20, 2022
Unsupervised Representation Learning by Invariance Propagation

Unsupervised Learning by Invariance Propagation This repository is the official implementation of Unsupervised Learning by Invariance Propagation. Pre

FengWang 15 Jul 06, 2022
Deep Learning applied to Integral data analysis

DeepIntegralCompton Deep Learning applied to Integral data analysis Module installation Move to the root directory of the project and execute : pip in

Thomas Vuillaume 1 Dec 10, 2021
Ground truth data for the Optical Character Recognition of Historical Classical Commentaries.

OCR Ground Truth for Historical Commentaries The dataset OCR ground truth for historical commentaries (GT4HistComment) was created from the public dom

Ajax Multi-Commentary 3 Sep 08, 2022
A PyTorch Implementation of PGL-SUM from "Combining Global and Local Attention with Positional Encoding for Video Summarization", Proc. IEEE ISM 2021

PGL-SUM: Combining Global and Local Attention with Positional Encoding for Video Summarization PyTorch Implementation of PGL-SUM From "PGL-SUM: Combin

Evlampios Apostolidis 35 Dec 22, 2022
Godot RL Agents is a fully Open Source packages that allows video game creators

Godot RL Agents The Godot RL Agents is a fully Open Source packages that allows video game creators, AI researchers and hobbiest the opportunity to le

Edward Beeching 326 Dec 30, 2022
ISBI 2022: Cross-level Contrastive Learning and Consistency Constraint for Semi-supervised Medical Image.

Cross-level Contrastive Learning and Consistency Constraint for Semi-supervised Medical Image Introduction This repository contains the PyTorch implem

25 Nov 09, 2022
Small-bets - Ergodic Experiment With Python

Ergodic Experiment Based on this video. Run this experiment with this command: p

Michael Brant 3 Jan 11, 2022
Detecting Blurred Ground-based Sky/Cloud Images

Detecting Blurred Ground-based Sky/Cloud Images With the spirit of reproducible research, this repository contains all the codes required to produce t

1 Oct 20, 2021
Program your own vulkan.gpuinfo.org query in Python. Used to determine baseline hardware for WebGPU.

query-gpuinfo-data License This software is not presently released under a license. The data in data/ is obtained under CC BY 4.0 as specified there.

Kai Ninomiya 5 Jul 18, 2022
Plotting points that lie on the intersection of the given curves using gradient descent.

Plotting intersection of curves using gradient descent Webapp Link --- What's the app about Why this app Plotting functions and their intersection. A

Divakar Verma 2 Jan 09, 2022
Serve TensorFlow ML models with TF-Serving and then create a Streamlit UI to use them

TensorFlow Serving + Streamlit! ✨ 🖼️ Serve TensorFlow ML models with TF-Serving and then create a Streamlit UI to use them! This is a pretty simple S

Álvaro Bartolomé 18 Jan 07, 2023
A package related to building quasi-fibration symmetries

qf A package related to building quasi-fibration symmetries. If you'd like to learn more about how it works, see the brief explanation and References

Paolo Boldi 1 Dec 01, 2021
Synthesizing Long-Term 3D Human Motion and Interaction in 3D in CVPR2021

Long-term-Motion-in-3D-Scenes This is an implementation of the CVPR'21 paper "Synthesizing Long-Term 3D Human Motion and Interaction in 3D". Please ch

Jiashun Wang 76 Dec 13, 2022