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?

  • 1
    $\begingroup$ 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). $\endgroup$
    – prubin
    Dec 4 '21 at 16:41
  • 1
    $\begingroup$ I think OP is referring to space complexity en.m.wikipedia.org/wiki/Space_complexity $\endgroup$
    – Kuifje
    Dec 6 '21 at 7:27
  • $\begingroup$ 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). $\endgroup$
    – Kuifje
    Dec 6 '21 at 7:28
  • $\begingroup$ 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. $\endgroup$
    – O. Sd
    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.

W.r.t. to your questions:

  • What would happen if the complexity exceeds the machine capacity?

Typically the solver & the computer will crash. Some commercial solvers have ways around this, e.g. CPLEX can store part of the BnB tree on the hard drive for very large problems/trees.

  • In this case, what would be the impact on the resolution time?

Assuming the computer doesn't crash, performance can be abysmal, but highly depends on implementation. For a bad implementation you would expect 100x-1000x worse performance. For a good implementation, it might only be 2x-5x worse.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.