Meta_CO

The official repository of the paper `unsupervised learning for combinatorial optimization needs meta learning' Haoyu Wang, Pan Li.

The repository contains the code and datasets contained in the max clique (MC), the minimum vertex covering (MVC), the max independent set (MIS) problems.

Environments

The environment requires Pytorch, Pytorch Geometric and some of the following key packages:

torch                   1.9.0
torch-cluster           1.5.9
torch-geometric         1.7.2
torch-scatter           2.0.8
torch-sparse            0.6.11
torch-spline-conv       1.2.1
tqdm                    4.62.2
networkx                2.5.1
numpy                   1.20.3
ogb                     1.3.5
pandas                  1.3.0
scikit-learn            0.24.2
scipy                   1.6.3
PyYAML                  5.4.1

To run the Gurobi9.5 baseline, you may also need to install Gurobi package and require the Gurobi permit

gurobipy                9.5.1

The Max Clique (MC)

STEP 1: data Preparation

1. 1 TWITTER

for twitter dataset, go to /max_clique/twitter/dataset/configs/config.yaml

enter the path to the folder that you would like to save the PyG form dataset in this yaml file, an example of the config.yaml file is shown as follows:

train:
    target_path: /...[your path].../meta_CO/max_clique/twitter/dataset/trainset
    data_dir: /...[your path].../meta_CO/max_clique/twitter/dataset/trainset

val:
    target_path: /...[your path].../meta_CO/max_clique/twitter/dataset/valset
    data_dir: /...[your path].../meta_CO/max_clique/twitter/dataset/valset

test:
    target_path: /...[your path].../meta_CO/max_clique/twitter/dataset/testset
    data_dir: /...[your path].../meta_CO/max_clique/twitter/dataset/testset

split and transform the original twitter dataset (which is shuffled and saved in /max_clique/twitter/dataset/raw_dataset, it needs unzip first), go to /max_clique/twitter/dataset and run:

python twitter_test.py
python twitter_train.py
python twitter_val.py

1. 2 RB200/500

for RB dataset, the data generation is adopted from the github repository of RUN-CSP.

here we use RB200 as an example: go to /max_clique/rb200/dataset/configs/config.yaml

enter the path to the folder that you would like to save the PyG form dataset in this yaml file, an example of the config.yaml file is shown as follows:

train:
    target_path: /...[your path].../meta_CO/max_clique/rb200/dataset/trainset
    data_dir: /...[your path].../meta_CO/max_clique/rb200/dataset/trainset

val:
    target_path: /...[your path].../meta_CO/max_clique/rb200/dataset/valset
    data_dir: /...[your path].../meta_CO/max_clique/rb200/dataset/valset

test:
    target_path: /...[your path].../meta_CO/max_clique/rb200/dataset/testset
    data_dir: /...[your path].../meta_CO/max_clique/rb200/dataset/testset

go to /max_clique/rb200/dataset to generate the training,val / testing data:

sh rb200_test.sh
sh rb200_train.sh
sh rb200_val.sh

STEP2: training

go to /max_clique/[dataset] folder, edit the maml.sh doc as you may want to, fill in the GPU number in utils.py (it should align with the gpu number in maml.sh) you are going to use, then run

sh maml.sh

To tun the Erdos goes neural (EGN) baseline, run

sh erdos.sh

STEP3: testing

go to /max_clique/[dataset] folder, open test.py, fill in the path to the model that you would like to test, then edit test.sh file, run

sh test.sh

for the problems, we provide our pre-trained model, in /max_clique/[dataset]/train_files/maml(erdos)/demo/best_model.pth, which could be used to directly solve the problems.

STEP4: fine-tuning

go to /max_clique/[dataset] folder, open finetune.py, fill in the path to the model that you would like to fine-tune, then edit finetune.sh file, run

sh finetune.sh

The Minimum Vertex Covering (MVC)

STEP 1: data Preparation

1. 1 TWITTER

for twitter dataset, go to /vertex_cover/twitter/dataset/configs/config.yaml

enter the path to the folder that you would like to save the PyG form dataset in this yaml file, an example of the config.yaml file is shown as follows:

train:
    target_path: /...[your path].../meta_CO/vertex_cover/twitter/dataset/trainset
    data_dir: /...[your path].../meta_CO/vertex_cover/twitter/dataset/trainset

val:
    target_path: /...[your path].../meta_CO/vertex_cover/twitter/dataset/valset
    data_dir: /...[your path].../meta_CO/vertex_cover/twitter/dataset/valset

test:
    target_path: /...[your path].../meta_CO/vertex_cover/twitter/dataset/testset
    data_dir: /...[your path].../meta_CO/vertex_cover/twitter/dataset/testset

split and transform the original twitter dataset (which is shuffled and saved in /vertex_cover/twitter/dataset/raw_dataset, it needs unzip first), go to /vertex_cover/twitter/dataset and run:

python twitter_test.py
python twitter_train.py
python twitter_val.py

1. 2 RB200/500

for RB dataset, the data generation is adopted from the github repository of RUN-CSP.

here we use RB200 as an example: go to /vertex_cover/rb200/dataset/configs/config.yaml

enter the path to the folder that you would like to save the PyG form dataset in this yaml file, an example of the config.yaml file is shown as follows:

train:
    target_path: /...[your path].../meta_CO/vertex_cover/rb200/dataset/trainset
    data_dir: /...[your path].../meta_CO/vertex_cover/rb200/dataset/trainset

val:
    target_path: /...[your path].../meta_CO/vertex_cover/rb200/dataset/valset
    data_dir: /...[your path].../meta_CO/vertex_cover/rb200/dataset/valset

test:
    target_path: /...[your path].../meta_CO/vertex_cover/rb200/dataset/testset
    data_dir: /...[your path].../meta_CO/vertex_cover/rb200/dataset/testset

go to /vertex_cover/rb200/dataset to generate the training,val / testing data:

sh rb200_test.sh
sh rb200_train.sh
sh rb200_val.sh

STEP2: training

go to /vertex_cover/[dataset] folder, edit the maml.sh doc as you may want to, fill in the GPU number in utils.py (it should align with the gpu number in maml.sh) you are going to use, then run

sh maml.sh

To tun the Erdos goes neural (EGN) baseline, run

sh erdos.sh

STEP3: testing

go to /vertex_cover/[dataset] folder, open test.py, fill in the path to the model that you would like to test, then edit test.sh file, run

sh test.sh

for the problems, we provide our pre-trained model, in /vertex_cover/[dataset]/train_files/erdos(maml)/demo/best_model.pth, which could be used to directly solve the problems.

STEP4: fine-tuning

go to /vertex_cover/[dataset] folder, open finetune.py, fill in the path to the model that you would like to fine-tune, then edit finetune.sh file, run

sh finetune.sh

The Max Independent Set (MIS)

Code is coming soon

Reference

If you find our paper or repo useful, please cite our paper:

@article{wang2023unsupervised,
  title={Unsupervised Learning for Combinatorial Optimization Needs Meta-Learning},
  author={Wang, Haoyu and Li, Pan},
  journal={International Conference on Learning Representations},
  year={2023}
}