isl-org/nphard

Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search

Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search

This is a tensorflow implementation of solving the maximum indepedent set problem using graph convolutional networks and guided tree search. The graph convolutional networks implementation is based on GCN (MIT License).

Setup

Requirement

Required python libraries: Tensorflow (>=1.3) + Scipy + Numpy.

Tested in Ubuntu 16.04 LTS + Intel i7 CPU + Nvidia Titan X (Pascal) with Cuda (>=8.0) and CuDNN (>=6.0). CPU mode should also work with no/minor changes.

Quick Start (Testing)

• Note the result produced here is without graph reduction and local search. If you wish to use them, please see the instructions in the next subsection.

1. Clone this repository.
2. Run "python demo.py" or "python demo_parallel.py" to solve the problem instance(s) in the "data" folder.
3. The result will be saved in "res_600".

Instructions for using graph reduction and local search

1. Clone KaMIS (GPLv2 License) from its Project or GitHub page.
2. Copy the files in "kernel" of this repo to "KaMIS" and run make. This will generate a shared object file "libreduce.so".
3. Copy "libreduce.so" back to "kernel".
4. Uncomment lines 8, 20, 87, 109, 272, 300 and comment 88, 110, 273 in "demo_parallel.py" to enhance it with graph reduction and local search. "demo.py" can be modified accordingly to include these components.
5. Rerun "demo_parallel.py" to see the difference.

Training

Run "train.py" to start training. Note that the training data is not provided and should be downloaded or synthesized from other sources, e.g.,

SATLIB (https://www.cs.ubc.ca/~hoos/SATLIB/benchm.html)

RB Model (https://github.com/notbad/RB)

The data file should contain an adjacency matrix and at least one groundtruth label, and saved in a MATLAB file with "adj" and "indset_label" symbols. The default data path is defined as data_path = "./data/CBS_Graph".

Citation

If you use our code for research, please cite our paper:

Zhuwen Li, Qifeng Chen and Vladlen Koltun. Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search. In NIPS 2018.

Todo List

1. Implement graph reduction and local search, and release them under MIT License

Question

If you have any question or request about the code and data, please email me at [email protected].

License

MIT License

nphard's Issues

Model

Hi,
Is the model file under the "model" directory a trained model upon the training dataset of SATLIB?

Can't get normal test result and I am confused.

Hi,
Thank you for your paper and sorry for interrupting you when you are busy with work. I'm trying to test this network with some datasets, however i can't get normal result.

My ubuntu server meets requirement, tensorflow-gpu 1.50 works well and Instructions for using graph reduction and local search also has done.

Q: Can't get normal test result
I use CBS_k3_n100_m403_b10 [100 variables, 403 clause] one of the SATLIB dataset to test.
My reduction from 3SAT to MAXINDSET easy script as follow:

import re
import numpy as np
import scipy.sparse as sp
import scipy.io as sio

with open("../CBS_k3_n100_m403_b10/CBS_k3_n100_m403_b10_1.cnf") as f:
    lines =  f.readlines()
lines.pop(0)
problem=[]
for line in lines:
    line = re.sub(r"0\n", "", line)
    problem.append([int(tmp) for tmp in line.split()])

num_clause = len(problem) 
num_node = 3 * num_clause

all_node = []
for i in range(num_clause):
    all_node += problem[i]
all_node = dict(enumerate(all_node))

matrix_dense = np.zeros((num_node, num_node), dtype=np.int)

for k1, v1 in all_node.items():
    for k2, v2 in all_node.items():
        if -v1 == v2:
            matrix_dense[k1, k2] = 1

s = sp.csr_matrix(m_dense)
sio.savemat("./test1_403.mat", {"adj":s})

if the number of independent set output by the model with size equal to the number of clauses, the formula is satisfiable; otherwise, it is not. However, the network output is 744 which is much larger than 403. and it takes almost 10 minutes to test in a graph which is also much larger than average 11.47s. I've tested a lot of data and still haven't got the ideal results

python demo_parallel.py

result = sio.loadmat("./res_0600/test1_403.mat")
label = result['nIS_vec']
print(np.sum(label>=1))

I didn't modify any code. I just used the provided model to test the data. I wanted to know what went wrong. thanks!!.

Mention more modern implementation

This project was implemented for TensorFlow v1. It appears that several forks have tried to modify it to run it in TensorFlow 2's compatibility mode.

Additionally to these adaptations, this algorithm has also been reimplemented in PyTorch using the well-established Deep Graph Library (DGL) as part of a recent publication.
Mentioning this in the README could be very helpful for people willing to use or test this algorithm.

Dataset

Can you share your dataset SATLIB?