$\mathcal{O}(1)$ memory handling

Obviously, the B&B routine needs to store every live node, during the search. This itself leads to a large number of required allocations and de-allocations of memory area. Further more, the heuristic in the final implementation require a large number of similar memory operations.

Deallocation is usually efficient, but allocation can require many clock-cycles, and can even have a run-time which is dependent on the number of allocated memory areas, depending on the platform on which the optimizer is run of course. Since both the number of allocated areas, and the number of allocations is mind-boggling, this itself could prove a significant bottleneck in the overall run-time of the optimizer.

Therefore, an efficient memory sub-system was implemented. This sub-system allocates a large (and hopefully large enough) memory area, which is then split in parts of the size needed by the B&B routine and the heuristic. Allocation can then be done by a special function call, and will always run in $\mathcal{O}(1)$ time. De-allocation has the same complexity. If the memory area is exhausted, the system will fail (simply abort the program with an error message). Of course, a more dynamical memory handler could have been implemented, but I found that it wasn't worth the effort, since just allocating a large enough area initially was practically possible. Besides, the page handling in modern operating systems lets us allocate much more memory than we actually use, without taking performance hits.

<