GenericTensorNetworks
Overview
GenericTensorNetworks is a high-performance package that uses tensor network algorithms to solve challenging combinatorial optimization problems. This approach allows us to efficiently compute various solution space properties that would be intractable with traditional methods.
Key Capabilities
Our package can compute a wide range of solution space properties:
- Maximum and minimum solution sizes
- Solution counts at specific sizes
- Complete enumeration of solutions
- Statistical sampling from the solution space
Supported Problem Classes
GenericTensorNetworks can solve many important combinatorial problems:
- Independent Set Problem
- Maximal Independent Set Problem
- Spin-Glass Problem
- Maximum Cut Problem
- Vertex Matching Problem
- Binary Paint Shop Problem
- Graph Coloring Problem
- Dominating Set Problem
- Boolean Satisfiability Problem
- Set Packing Problem
- Set Covering Problem
Scientific Background
For the theoretical foundation and algorithmic details, please refer to our paper: "Computing properties of independent sets by generic programming tensor networks"
If you find our package useful in your research, please cite our work using the references in CITATION.bib.
Getting Started
Installation
Installation instructions are available in our README.
Basic Example
Here's a simple example that computes the independence polynomial of a random regular graph:
using GenericTensorNetworks, Graphs # Add CUDA for GPU acceleration
# Create and solve a problem instance
result = solve(
GenericTensorNetwork(
IndependentSet(
Graphs.random_regular_graph(20, 3), # Graph to analyze
UnitWeight(20) # Uniform vertex weights
);
optimizer = TreeSA(), # Contraction order optimizer
openvertices = (), # No open vertices
fixedvertices = Dict() # No fixed vertices
),
GraphPolynomial(); # Property to compute
usecuda = false # Use CPU (set true for GPU)
)
Understanding the API
The main function solve
takes three components:
Problem Instance: Created with
GenericTensorNetwork
, which wraps problem types likeIndependentSet
- The first argument defines the problem (graph and weights)
- Optional arguments control the tensor network construction:
optimizer
: Algorithm for finding efficient contraction ordersopenvertices
: Degrees of freedom to leave uncontractedfixedvertices
: Variables with fixed assignments
Property to Compute: Such as
GraphPolynomial
,SizeMax
, orConfigsAll
Computation Options: Like
usecuda
to enable GPU acceleration
Note: The first execution will be slower due to Julia's just-in-time compilation. Subsequent runs will be much faster.
API Structure
The following diagram illustrates the possible combinations of inputs:
⠀
Functions in the Graph
box are primarily from the Graphs package, while the rest are defined in GenericTensorNetworks.
Next Steps
For a deeper understanding, we recommend starting with the Independent Set Problem example, which demonstrates the core functionality of the package. ```