Research /
AvoidingDistance1
Required: sage, cplex (installed in $HOME/cplex) and linux (64 bits)
Download files: avoidingDistance1.zip
Howto : compute the weighted independence number of a graph with cplex
- input graph file format : see graphw_example.dat for an example (its weighted independence number is 10)
- a basic integer linear programming formulation is provided in weightedIndependentNumber.mod (mod format)
- use script computeWeightedIndependentNumber.sh to run the computation
> bash computeWeightedIndependentNumber.sh input_graph.dat
Howto : build the unit distance graph achieving the bound 0.256459
- the list L of the vertices is in the file : W_circles_607_vertices.sage
- compute the edges W_circles_607_edges.sage of the unit-distance graph from L with the sage script makeEdges.sage:
> sage makeEdges.sage W_circles_607_vertices.sage W_circles_607_edges.sage
- given weights are in the file W_circles_607_weights.sage
---
Description of main files
- weightedIndependentNumber.mod: model file for the weighted independent number (OPL syntax)
- graphw_example.dat: example of data file fot the weighted independant number
- makeEdges.sage: sage script to build the edges of the unit distance graphs from the list of its vertices
- makeDatFile.sage: sage script to build the data file from the list of edges of a graph and the list of vertices weights
Usage
# make edges from vertices sage makeEdges.sage inputFileVertices.sage outputFileVertices.sage # make dat file for cplex sage makeDatFile.sage inputFileEdges.sage inputFileWeights.sage outputFile.dat # solve with cplex bash computeWeightedIndependentNumber.sh outputFile.dat
Specific files for the graph W_circles_607
The corresponding files for the graph `W_circles_607` are provided for conveniency to reproduce easyly the upper bound 0.256459:
- W_circles_607_vertices.sage : file of vertices
- W_circles_607_weights.sage : file of weights (total sum = 1.0)
- W_circles_607_integer_weights.sage : file of integer weights (total sum = 1 999 983)
- W_circles_607_edges.sage : file of edges (output of makeEdges.sage from the file of vertices)
- W_circles_607.dat : input file for solving the weighted independent number (output of makeDatFile.sage from the two previous files of edges and weights as input files)
- run_W_Circles_607.sh: bash script reproducing the computation of the weighted independent number of W_circles_607, starting from the list of its vertices and weights