Expression rewritting based simulated annealing

[GiggleLiu]

See: https://arxiv.org/abs/2108.05665

Example:

using LightGraphs, OMEinsum, OMEinsumContractionOrders, Random

function random_regular_eincode(n, k)
    g = LightGraphs.random_regular_graph(n, k)
    ixs = [minmax(e.src,e.dst) for e in LightGraphs.edges(g)]
    return EinCode((ixs..., [(i,) for i in LightGraphs.vertices(g)]...), ())
end

Random.seed!(2)
g = random_regular_graph(220, 3)
code = random_regular_eincode(220, 3)
res = optimize_greedy(code,uniformsize(code, 2))
tc, sc = OMEinsum.timespace_complexity(res, uniformsize(code, 2))
# (43.585434215845986, 35.0)

optcode = optimize_tree(res,uniformsize(code, 2); sc_target=28, βs=0.1:0.1:10, ntrials=2, niters=100, sc_weight=3.0)
tc, sc = OMEinsum.timespace_complexity(optcode, uniformsize(code, 2))
# (34.70897386429041, 30.0)

[codecov[bot]]

Codecov Report

Merging #9 (494f9ba) into master (e9c03aa) will decrease coverage by 0.89%. The diff coverage is 93.33%.

@@            Coverage Diff             @@
##           master       #9      +/-   ##
==========================================
- Coverage   95.34%   94.45%   -0.90%     
==========================================
  Files           2        3       +1     
  Lines         258      433     +175     
==========================================
+ Hits          246      409     +163     
- Misses         12       24      +12     

Impacted Files	Coverage Δ
src/treesa.jl	93.14% <93.14%> (ø)
src/sa.jl	97.45% <100.00%> (ø)

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update e9c03aa...494f9ba. Read the comment docs.