Spatial complexity of optimization algorithm

How can I calculate the space complexity of an optimization algorithm?

Otherwise, what would happen if the complexity exceeds the machine capacity, and can I use the hardware instead of RAM? In this case, what would be the impact on the resolution time?

• What do you mean by the "spatial complexity of an optimization algorithm"? The phrase "spatial complexity" is usually employed when describing a surface of solid object (en.wikipedia.org/wiki/Spatial_complexity). Dec 4 '21 at 16:41
• I think OP is referring to space complexity en.m.wikipedia.org/wiki/Space_complexity Dec 6 '21 at 7:27
• Could you detail the algorithm ? To evaluate the computational complexity of an algorithm (time or space), you must analyse its structure (number of loops and elementary operations). Dec 6 '21 at 7:28
• Sorry I re edited the question. I want to know how much space will occupy ech node generated in a b&b algorithm ( for warm or hot starting) and what would be the consequences if the total space of the waiting line exeeds de ram capacitiy. Dec 6 '21 at 9:47

It is very flaky to calculate this theoretically, as it's very implementation dependent. Depending on the spatial efficiency of the data structures, caching, and so on, it can vary from sublinear all the way to factorial.

Let me give you a few examples. In BnB, all we really need to store is the bounds of all variables for every node of the BnB tree. Ergo, the spatial complexity should be 2*nu_vars*nu_nodes.

However, we might also use some hash maps to look up information internally, and depending on the implementation this might scale cubicaly or worse. We might also use a git-style diff technique to only store bounds changes instead of actual bounds, which could reduce the average runtime complexity to sublinear.

Solvers being the complex pieces of software they are, other information might be stored, such as conflicts for conflict analysis, restoration information, and so on. For (MI)NLPs, the way the hessian is calculated can also affect memory usage considerably. For a good implementation that would have a constant spatial overhead (as in it doesn't scale with the number of nodes), but some solvers don't do this very well.

Solvers might also store warm starting information for some nodes (but not all of them), which can also induce a memory overhead that scales with the number of nodes in a non-obvious way (since it's governed by a heuristic).

Finally, if a solver generates cuts dynamically, then this also induces a hard to calculate memory overhead. There are typically limits on pool sizes and sizes of cuts, but these can also change on the fly depending on the implementation.