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]">
1st Solution For ICDAR 2021 Competition on Mathematical Formula Detection

This project releases our 1st place solution on ICDAR 2021 Competition on Mathematical Formula Detection. We implement our solution based on MMDetection, which is an open source object detection tool

yuxzho 94 Dec 25, 2022
Out-of-Domain Human Mesh Reconstruction via Dynamic Bilevel Online Adaptation

DynaBOA Code repositoty for the paper: Out-of-Domain Human Mesh Reconstruction via Dynamic Bilevel Online Adaptation Shanyan Guan, Jingwei Xu, Michell

197 Jan 07, 2023
Bayesian Deep Learning and Deep Reinforcement Learning for Object Shape Error Response and Correction of Manufacturing Systems

Bayesian Deep Learning for Manufacturing 2.0 (dlmfg) Object Shape Error Response (OSER) Digital Lifecycle Management - In Process Quality Improvement

Sumit Sinha 30 Oct 31, 2022
Supplemental learning materials for "Fourier Feature Networks and Neural Volume Rendering"

Fourier Feature Networks and Neural Volume Rendering This repository is a companion to a lecture given at the University of Cambridge Engineering Depa

Matthew A Johnson 133 Dec 26, 2022
Official implementation of our paper "Learning to Bootstrap for Combating Label Noise"

Learning to Bootstrap for Combating Label Noise This repo is the official implementation of our paper "Learning to Bootstrap for Combating Label Noise

21 Apr 09, 2022
PyTorchVideo is a deeplearning library with a focus on video understanding work

PyTorchVideo is a deeplearning library with a focus on video understanding work. PytorchVideo provides resusable, modular and efficient components needed to accelerate the video understanding researc

Facebook Research 2.7k Jan 07, 2023
Cold Brew: Distilling Graph Node Representations with Incomplete or Missing Neighborhoods

Cold Brew: Distilling Graph Node Representations with Incomplete or Missing Neighborhoods Introduction Graph Neural Networks (GNNs) have demonstrated

37 Dec 15, 2022
Reinfore learning tool box, contains trpo, a3c algorithm for continous action space

RL_toolbox all the algorithm is running on pycharm IDE, or the package loss error may exist. implemented algorithm: trpo a3c a3c:for continous action

yupei.wu 44 Oct 10, 2022
K-Means Clustering and Hierarchical Clustering Unsupervised Learning Solution in Python3.

Unsupervised Learning - K-Means Clustering and Hierarchical Clustering - The Heritage Foundation's Economic Freedom Index Analysis 2019 - By David Sal

David Salako 1 Jan 12, 2022
PyTorch code for our paper "Attention in Attention Network for Image Super-Resolution"

Under construction... Attention in Attention Network for Image Super-Resolution (A2N) This repository is an PyTorch implementation of the paper "Atten

Haoyu Chen 71 Dec 30, 2022
Erpnext app for make employee salary on payroll entry based on one or more project with percentage for all project equal 100 %

Project Payroll this app for make payroll for employee based on projects like project on 30 % and project 2 70 % as account dimension it makes genral

Ibrahim Morghim 8 Jan 02, 2023
Yolov5+SlowFast: Realtime Action Detection Based on PytorchVideo

Yolov5+SlowFast: Realtime Action Detection A realtime action detection frame work based on PytorchVideo. Here are some details about our modification:

WuFan 181 Dec 30, 2022
Code repo for EMNLP21 paper "Zero-Shot Information Extraction as a Unified Text-to-Triple Translation"

Zero-Shot Information Extraction as a Unified Text-to-Triple Translation Source code repo for paper Zero-Shot Information Extraction as a Unified Text

cgraywang 88 Dec 31, 2022
pytorch implementation of ABC : Auxiliary Balanced Classifier for Class-imbalanced Semi-supervised Learning

ABC:Auxiliary Balanced Classifier for Class-imbalanced Semi-supervised Learning, NeurIPS 2021 pytorch implementation of ABC : Auxiliary Balanced Class

Hyuck Lee 25 Dec 22, 2022
Deep deconfounded recommender (Deep-Deconf) for paper "Deep causal reasoning for recommendations"

Deep Causal Reasoning for Recommender Systems The codes are associated with the following paper: Deep Causal Reasoning for Recommendations, Yaochen Zh

Yaochen Zhu 22 Oct 15, 2022
Machine Learning Models were applied to predict the mass of the brain based on gender, age ranges, and head size.

Brain Weight in Humans Variations of head sizes and brain weights in humans Kaggle dataset obtained from this link by Anubhab Swain. Image obtained fr

Anne Livia 1 Feb 02, 2022
This is a GUI interface which can process forest fire detection, smoke detection and fire segmentation

This is a GUI interface which can process forest fire detection, smoke detection and fire segmentation. Yolov5 is used to detect fire and smoke and unet is used to segment fire.

7 Jan 08, 2023
BT-Unet: A-Self-supervised-learning-framework-for-biomedical-image-segmentation-using-Barlow-Twins

BT-Unet: A-Self-supervised-learning-framework-for-biomedical-image-segmentation-using-Barlow-Twins Deep learning has brought most profound contributio

Narinder Singh Punn 12 Dec 04, 2022
Implementation of Stochastic Image-to-Video Synthesis using cINNs.

Stochastic Image-to-Video Synthesis using cINNs Official PyTorch implementation of Stochastic Image-to-Video Synthesis using cINNs accepted to CVPR202

CompVis Heidelberg 135 Dec 28, 2022