Faster 'dp' for asymptotic contractions

[jcmgray]

If you try the 'dp' optimizer on this contraction (a tree graph taken from #112):

'ab,ab,bc,bc,ce,ce,ei,ei,ej,ej,cf,cf,fk,fk,fl,fl,bd,bd,dg,dg,gm,gm,gn,gn,dh,dh,ho,ho,hp,hp->'

it's veeery slow for shapes=[(2, 2)] * 30 but very fast in the asymptotic case where the dimensions get bigger, e.g. for shapes=[(100, 100)] * 30. However, it finds the same path in both cases.

Is this just some quirk on the cost_cap strategy or can we take advantage of this more generally to make 'dp' faster? Are there contractions where scaling up all the dimensions by the same factor leads to different sub-optimal paths for the original contraction?

cc @mrader1248

[mrader1248]

Is it correct that this is not yet solved? Does any of the visual representations in the mentioned issue correspond to the contraction above?

[yaroslavvb]

It's the complete binary tree of depth 5

Behavior is still present in master, this colab is an easy way to reproduce
https://colab.research.google.com/drive/14JwffnpbyxlQUv93js7JzZ2j38VIE2FD

Search time jumps 150x when going from factor size 10,10 to factor size 9,9

[dgasmith]

@mrader1248 Do you have a bit of time to look into this?

[yaroslavvb]

A work-around is to use size option when creating optimizer, the slowdown is not observed in such case. IE opt=DynamicProgramming(minimize='size')

I'm curious why this algorithm gives such a jump in computation time for a tree but not for a chain, they should have the same complexity.