Good day to all!

In this small post I will continue the topic that I raised in my old two posts
Part 1
Part 2

Namely, I will talk about a small idea that recently came to my mind, and which helps to solve the set task a little better.

So welcome under habrakat

Old solution

If you remember, or read the first two parts, my final decision was based on the branch and bound method and a tricky selection of heuristics and algorithm parameters. Is it possible to somehow impart 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 for ages."
What do I mean by this? Let's give that solution, which at some step seemed to us very good, to save and not throw it out of consideration, even if after a few 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? As it seems to me, this will help to avoid situations that a good solution that has a surge in value somewhere at the beginning will be thrown out of consideration, because there are many solutions that are very cheap at first, but at the end they become much more expensive. Then the idea of ​​not forgetting and not throwing out anything will help us at the end to see and understand that this is a 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 a better solution is more than 30% less than other current decisions, then we remember this branch of the decision. And then, if we see a cost increase for the best solution large enough (in my case it looked like this - if at one step more than 5% of the total cost of the best solution is added), then we rollback, namely roll back, and look, not Will the saved solution give us a better solution?

One way or another, it worked. On the same graph in which the algorithms of the first two posts were checked, I got a gain of 3.5% from the best solution.

What do you think about this?