GNN&GBDT-Guided Fast Optimizing Framework for Large-scale Integer Programming

Contact

Welcome to academic and business collaborations with funding support. For more details, please contact us via email at xuhua@tsinghua.edu.cn.

Overview

This release contains the key processes of the GNN&GBDT-Guided Fast Optimizing Framework, as described in the paper. The provided code implements the main components of the approach, covering data generation, training, and inference. We also provide interfaces that are left to be implemented by the user so that the code can be flexibly used in different contexts.

The following gives a brief overview of the contents; more detailed documentation is available within each file:

• Code/data_generation.py: Generating integer programming problems for training and testing.
• Code/data_solution.py: Generate optimal solutions to integer programming problems for training.
• Code/data_partition.py: Generate graph partition results for bipartite graph representations of integer programming problems used for training.
• Code/GNN_train.py: Use prepared training data to train GNN to generate neural embeddings of decision variables.
• Code/GNN_inference.py: Using a trained GNN to generate neural embeddings of decision variables for training data.
• Code/GBDT_train.py: Train GBDT using the training data and the resulting neural embeddings results.
• Code/test.py: Run test data to get optimized results.
• Code/model/graphcnn.py: GNN model.
• Code/model/gbdt_regressor.py: GBDT model.
• Result/CA: Running results of the very large-scale version of the Combinatorial Auction problem.
• Result/MIS: Running results of the very large-scale version of the Maximum Independent Set problem.
• Result/MVC: Running results of the very large-scale version of the Minimum Vertex Covering problem.
• Result/SC: Running results of the very large-scale version of the Set Covering problem.
• Paper/paper.pdf: PDF version of the paper.

Requirements

The required environment is shown in GNN_GBDT.yml.

Usage

1. Implement the interfaces respectively.

2. Perform training according to the following code running order:

   Code/data_generation.py
   Code/data_solution.py
   Code/data_partition.py
   Code/GNN_train.py
   Code/GNN_inference.py
   Code/GBDT_train.py
   

3. Run tests with test.py.

Citing this work

Paper: GNN&GBDT-Guided Fast Optimizing Framework for Large-scale Integer Programming

If you use the code here please cite this paper:

@inproceedings{ye2023gnn,
  title={GNN\&GBDT-Guided Fast Optimizing Framework for Large-scale Integer Programming},
  author={Ye, Huigen and Xu, Hua and Wang, Hongyan and Wang, Chengming and Jiang, Yu},
  booktitle={ICML},
  year={2023}
}