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