mwis-vr-instances-dataset/s3://mwis-vr-instances

MWIS-VR-Instances

This repository contains instances of maximum weight independent set problems
described in the paper vrInstances.pdf located in the repository.

There are 38 instances, each one corresponding to a directory archived as a 
gzipped tar file.

For an undirected, node-weighted graph G = (V,E,w) with N nodes, M edges 
and integral node IDs from [1, N], the directory contains the following files:

• instance name.txt – Name of the instance.
• conflict graph.txt – Edges of G. The file has a total of M + 1 lines. 
The first line gives the numbers of nodes and edges: “N M”. 
Each of the lines 2, . . . , M + 1 describes an edge e = (u, v) ∈ E as “u v”.
• node weights.txt – Node weights. The file has a total of N lines, each
describing the weight of node v ∈ V as “v w(v)”. The weights are integers.
• solution.txt – Initial solution for warm start. 
It contains one line per node in the initial solution, giving its node 
index: if a node v in the solution, the file contains a line with “v” in it.
• cliques.txt – Set of cliques in G. 
For each clique C = {c1,c2,...,ck}, the file contains one line as 
“c1 c2 . . . ck”.
• lploads.txt – Solution for the relaxed LP problem for the MWIS problem
on the clique graph, where each node v ∈ V has a relaxed LP value 
l(v) ∈ [0,1]. 
The file has N lines, each with the LP value of a node v ∈ V as “v l(v)”, where l(v) is a floating point number. 

The files of MWIS instances making up this repository are:


        MT-D-01.tar.gz
        MT-D-200.tar.gz
        MT-D-FN.tar.gz
        MT-W-01.tar.gz
        MT-W-200.tar.gz
        MT-W-FN.tar.gz
        MR-D-01.tar.gz
        MR-D-03.tar.gz
        MR-D-05.tar.gz
        MR-D-FN.tar.gz
        MR-W-FN.tar.gz
        MW-D-01.tar.gz
        MW-D-20.tar.gz
        MW-D-40.tar.gz
        MW-D-FN.tar.gz
        MW-W-01.tar.gz
        MW-W-05.tar.gz
        MW-W-10.tar.gz
        MW-W-FN.tar.gz
        CW-T-C-1.tar.gz
        CW-T-C-2.tar.gz
        CW-T-D-4.tar.gz
        CW-T-D-6.tar.gz
        CR-T-C-1.tar.gz
        CR-T-C-2.tar.gz
        CR-T-D-4.tar.gz
        CR-T-D-6.tar.gz
        CR-T-D-7.tar.gz
        CW-S-L-1.tar.gz
        CW-S-L-2.tar.gz
        CW-S-L-4.tar.gz
        CW-S-L-6.tar.gz
        CW-S-L-7.tar.gz
        CR-S-L-1.tar.gz
        CR-S-L-2.tar.gz
        CR-S-L-4.tar.gz
        CR-S-L-6.tar.gz
        CR-S-L-7.tar.gz

Download each file.  Then to create a directory named DIR from the file 
DIR.tar.gz with the instances description, run

gunzip DIR.tar.gz
tar xvf DIR.tar

For questions, contact

Mauricio G.C. Resende: mgcr@berkeley.edu
Andrew V. Goldberg: avg@alum.mit.edu
Quico Spaen: qspaen@berkeley.edu