Adaptive termination

[triceo]

Absolute terminations (such as time spent, unimproved time spent etc.) are not good enough, because they require a different configuration for every problem and every data set. (You need to know how long to solve for.) We want to provide a new kind of termination, which is only configured in relative terms - not in absolute time, or absolute score difference.

Please see the proposal. We define several parameters:

• A time window G, a time interval. Default value proposed to be 30 seconds.
• A score difference D, a ratio of two the first and the last score. Default value proposed to be 0.01, or 1 %.

The termination would work like this:

1. The grace period starts and has a length of G. During the grace period, termination is not allowed.
2. At the end of the grace period, a softest score is read, and compared to the softest score at the beginning of the grace period. The difference of the two becomes Y_1. If Y_1 == 0, immediate termination.
3. In the next move, a time windows T_N is established, by subtracting G from the current time. The softest score at the end of T_N (= the current score) is compared to the softest score at the beginning of T_N, and the difference becomes Y_N.
4. Y = Y_N/Y_1. If D > Y, terminate. Otherwise:
5. Back to 3, or back to 1 if the softest-but-last score level changed. If the score only has one level, back to 3. If the score has multiple levels, the grace period re-starts (back to 1) every time the second-to-last level improves. Example: For HardSoftScore, the grace period restarts every time the hard score improves.

Naming not decided yet.