Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search
Authors: Zhuwen Li, Qifeng Chen, Vladlen Koltun
NeurIPS 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 5 ExperimentsThe presented approach is evaluated on four canonical NP-hard problems and five datasets, which include benchmark satisfiability problems and real social network graphs with up to a hundred thousand nodes. Experimental results demonstrate that the presented approach substantially outperforms recent deep learning work, and performs on par with highly optimized state-of-the-art heuristic solvers for some NP-hard problems. |
| Researcher Affiliation | Collaboration | Zhuwen Li Intel Labs Qifeng Chen HKUST Vladlen Koltun Intel Labs |
| Pseudocode | No | The complete basic algorithm, referred to as Basic MIS, is specified in the supplementary material. The revised algorithm is summarized in the supplement. The parallelized tree search algorithm is summarized in the supplement. |
| Open Source Code | No | We will release code to support future progress along this direction. |
| Open Datasets | Yes | Datasets. For training, we use the SATLIB benchmark [21]. ... We evaluate on other problems and datasets as follows: SAT Competition 2017 [4]... BUAA-MC [39]... SNAP Social Networks [27]... Citation networks [33]. |
| Dataset Splits | Yes | We partition the dataset at random into a training set of size 38,000, a validation set of size 1,000, and a test set of size 1,000. |
| Hardware Specification | Yes | Training proceeds for 200 epochs and takes about 16 hours on a desktop with an i7-5960X 3.0 GHz CPU and a Titan X GPU. |
| Software Dependencies | No | The paper mentions optimizers (Adam) and network architectures (GCN, ReLU) but does not provide specific version numbers for software dependencies such as programming languages, libraries, or frameworks used for their implementation. |
| Experiment Setup | Yes | Our network has L = 20 graph convolutional layers... The widths of the intermediate layers are identical: Cl = 32 for l = 1, . . . , L 1. The width of the output layer is CL = M, where M is the number of output maps. We use M = 32. ... We use Adam [23] with single-graph mini-batches and learning rate 10 4. Training proceeds for 200 epochs... |