GNN&GBDT-Guided Fast Optimizing Framework for Large-scale Integer Programming
Authors: Huigen Ye, Hua Xu, Hongyan Wang, Chengming Wang, Yu Jiang
ICML 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Extensive experiments show that the proposed framework can solve IPs with millions of scales and surpass SCIP and Gurobi in the specified wall-clock time using only a small-scale optimizer with 30% of the problem size. It also shows that the proposed framework can save 99% of running time in achieving the same solution quality as SCIP, which verifies the effectiveness and efficiency of the proposed framework in solving large-scale IPs. |
| Researcher Affiliation | Collaboration | Huigen Ye 1 2 Hua Xu 1 2 Hongyan Wang 1 2 Chengming Wang 3 Yu Jiang 3 1State Key Laboratory of Intelligent Technology and Systems, Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China 2Beijing National Research Center for Information Science and Technology(BNRist), Beijing 100084, China 3Meituan Inc., Block F&G, Wangjing International R&D Park, No.6 Wang Jing East Rd, Chaoyang District, Beijing, 100102, China. |
| Pseudocode | Yes | The paper contains 'Algorithm 1 Initial Solution Search', 'Algorithm 2 Neighborhood Search', 'Algorithm 3 Neighborhood Crossover', 'Algorithm 4 FENNEL-based Graph Partition Algorithm', and 'Algorithm 5 REPAIR Algorithm'. |
| Open Source Code | Yes | Code for reproducing all the experiments can be found at https://github.com/thuiar/GNN-GBDT-Guided Fast-Optimizing-Framework. |
| Open Datasets | No | For the four widely used NP-hard benchmark IPs, the existing data set cannot meet such large-scale data requirements, so we use data generators to generate training and test data sets. Specifically, for the Maximum Independent Set problem (MIS) or Minimum Vertex Covering problem (MVC) with n decision variables and m constraints, we generate a random graph with n nodes and m edges to correspond to an IP problem that meets the scale requirements. For the Combinatorial Auction problem (CA) with n decision variables and m constraints, we generate a random problem with n items and m bids where each bid includes 5 items. For the Set Covering problem (SC) with n decision variables and m constraints, we generate a random problem with n items and m sets where each set bid includes 4 items. The paper describes how these datasets were generated but does not provide any specific link, DOI, or formal citation for public access to the generated data instances themselves. |
| Dataset Splits | No | The paper mentions 'training and test data sets' but does not provide specific details on dataset splits (e.g., percentages, counts for train/validation/test sets), nor does it explicitly mention a validation set. It only states 'For the optimal solution in the training data set, we use Gurobi to run for 8 hours to find the approximate optimal solution.' |
| Hardware Specification | Yes | All experiments are run on a machine with two Intel Xeon Platinum 8375C @ 2.90GHz CPU and four NVIDIA TESLA V100(32G) GPU. |
| Software Dependencies | Yes | In this paper, the state-of-the-art IP solvers SCIP (Achterberg, 2009) and Gurobi(10.0) are used as the baseline, and their scale-constrained versions are used as the small-scale optimizer for neighborhood optimization. |
| Experiment Setup | Yes | In addition, on all IPs, we set that the running time of a round of the search with fixed radius cannot exceed 20% of the total time. In particular, for the CA problem, due to the huge search space of the initial solution, it is easy to exceed the memory limit of the experimental machine. In the experiments with proportion α = 50%, our initial solution is still carried out using proportion α = 30% of the weakened version. |