GenericTensorNetworks

This package implements generic tensor networks to compute solution space properties of a class of hard combinatorial problems. The solution space properties include

• The maximum/minimum solution sizes,
• The number of solutions at certain sizes,
• The enumeration of solutions at certain sizes.
• The direct sampling of solutions at certain sizes.

The solvable problems include Independent set problem, Maximal independent set problem, Spin-glass problem, Cutting problem, Vertex matching problem, Binary paint shop problem, Coloring problem, Dominating set problem, Satisfiability problem, Set packing problem and Set covering problem.

Background knowledge

Please check our paper "Computing properties of independent sets by generic programming tensor networks". If you find our paper or software useful in your work, we would be grateful if you could cite our work. The CITATION.bib file in the root of this repository lists the relevant papers.

Quick start

You can find a set up guide in our README. To get started, open a Julia REPL and type the following code.

julia> using GenericTensorNetworks, Graphs

julia> # using CUDA

julia> solve(
           IndependentSet(
               Graphs.random_regular_graph(20, 3);
               optimizer = TreeSA(),
               weights = NoWeight(),    # default: uniform weight 1
               openvertices = (),       # default: no open vertices
               fixedvertices = Dict()   # default: no fixed vertices
           ),
           GraphPolynomial();
           usecuda=false              # the default value
       )
0-dimensional Array{Polynomial{BigInt, :x}, 0}:
Polynomial(1 + 20*x + 160*x^2 + 659*x^3 + 1500*x^4 + 1883*x^5 + 1223*x^6 + 347*x^7 + 25*x^8)

Here the main function solve takes three input arguments, the problem instance of type IndependentSet, the property instance of type GraphPolynomial and an optional key word argument usecuda to decide use GPU or not. If one wants to use GPU to accelerate the computation, the using CUDA statement must uncommented.

The problem instance takes four arguments to initialize, the only positional argument is the graph instance that one wants to solve, the key word argument optimizer is for specifying the tensor network optimization algorithm, the key word argument weights is for specifying the weights of vertices as either a vector or NoWeight(). The keyword argument openvertices is a tuple of labels for specifying the degrees of freedom not summed over, and fixedvertices is a label-value dictionary for specifying the fixed values of the degree of freedoms. Here, we use TreeSA method as the tensor network optimizer, and leave weights and openvertices the default values. The TreeSA method finds the best contraction order in most of our applications, while the default GreedyMethod runs the fastest.

The first execution of this function will be a bit slow due to Julia's just in time compiling. The subsequent runs will be fast. The following diagram lists possible combinations of input arguments, where functions in the Graph are mainly defined in the package Graphs, and the rest can be found in this package.

⠀ You can find many examples in this documentation, a good one to start with is Independent set problem.