Learning Combinatorial Optimization Algorithms over Graphs
Authors: Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, Le Song
NeurIPS 2017 | Conference PDF | Archive PDF | Plain Text | 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 {hanjun.dai, elias.khalil, yuyu.zhang, bdilkina, lsong}@cc.gatech.edu |
| 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. |