Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Learning Combinatorial Optimization Algorithms over Graphs
Authors: Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, Le Song
NeurIPS 2017 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 5 Experimental Evaluation Instance generation. To evaluate the proposed method against other approximation/heuristic algorithms and deep learning approaches, we generate graph instances for each of the three problems. |
| Researcher Affiliation | Collaboration | Hanjun Dai , Elias B. Khalil , Yuyu Zhang , Bistra Dilkina , Le Song College of Computing, Georgia Institute of Technology Ant Financial EMAIL |
| Pseudocode | Yes | Algorithm 1 Q-learning for the Greedy Algorithm |
| Open Source Code | Yes | We modify existing open-source code to implement both S2V-DQN 2 and PN-AC 3. Our code is publicly available 4. (Footnote 4: https://github.com/Hanjun-Dai/graph_comb_opt) |
| Open Datasets | Yes | In addition to the experiments for synthetic data, we identified sets of publicly available benchmark or real-world instances for each problem, and performed experiments on them. A summary of results is in Table 3, and details are given in Appendix C. (Table 3 mentions TSPLIB [32]) |
| Dataset Splits | Yes | S2V-DQN and PN-AC use 100 held-out graphs for validation, and we report the test results on another 1000 graphs. |
| Hardware Specification | Yes | For S2V-DQN and PN-AC, we use a CUDA K80-enabled cluster for training and testing. |
| Software Dependencies | Yes | We use CPLEX[17] to get optimal solutions for MVC and MAXCUT, and Concorde [3] for TSP (details in Appendix D.1). (Reference [17] states: IBM. CPLEX User s Manual, Version 12.6.1, 2014.) |
| Experiment Setup | Yes | For TSP, where the graph is fully-connected, we build the K-nearest neighbor graph (K = 10) to scale up to large graphs. |