Good day to all!

In this short post I will continue the theme that rises in their old two positions
Part 1
Part 2

Namely, talk about a small idea that has recently occurred to me, and that helps to solve the problem a little better.

So welcome to habrakat

Old decision

If you remember, or read the first two parts, my final decision was based on the branch-and-bound method and a cunning selection of heuristics and algorithm parameters. Is it possible to somehow impede the quality of the algorithm by adding changes to the algorithm itself?

Idea

The idea is quite simple - let's remember everyone with whom we felt good. In the style of “love forever”.
What do I mean by that? Let us make that decision, which at some step seemed very good to us, to keep and not to throw out of consideration, even if after several steps it seems to us to be completely bad? And then, if at some point we have a crisis of ideas and options, remember about it?
Theoretically, why is this and how can it help us? It seems to me that this will help to avoid situations that a good solution with a surge in value somewhere in the beginning will be thrown out of consideration, because there are many solutions that are very cheap at first, but in the end they become much more expensive. Then the idea of ​​not forgetting and not throwing anything away will help us in the end to see and understand that this is some kind of solution, expensive at the beginning, in the end it becomes much cheaper.

results

I added this idea to my algorithm. The conditions were as follows: if at some step the cost of the best solution is more than 30% less than the rest of the current solutions, then we remember this branch of the solution. And then, if we see the cost increase for the best solution large enough (in my case, it looked like this - if more than 5% of the total cost of the best solution is added at one step), then we do a rollback, namely roll back, and look, and not whether the saved option will give us a better solution.

Somehow, it worked. On the same graph on which the algorithms of the first two posts were tested, I got a 3.5% gain from the best solution.

What do you think about this?