Do we need probabilistic intensification?

[N-Wouda]

For CVRP, our default is already to always intensify (see configs/cvrp.toml). For VRPTW, we intensify 15% of the time, or when we find a new best solution (see configs/vrptw.toml). How much worse is it to always intensify for VRPTW as well, and remove the parameter altogether?

Benchmarks

On VRPTW and current main, since CVRP already does 100% and I do not propose we change that. Current main is eacde31981dfe354274bfd2c973ccbd80e63f631. One hour, average over ten seeds.

category	Never	Current (15%)	Always
C1	413476.4	413508.7	413505.4
C2	161968.6	161899.1	161899.1
R1	473631.6	473244.7	473185.8
R2	276960.7	277035.6	277338.1
RC1	442861.8	442598.2	442229.6
RC2	232205.0	232231.6	232349.2

Never behaves as if route operators do not exist at all, so there is also no intensification for new best solutions.

Job IDs: - Never: 3082452 - Current: 3071365 - Always: 3082871 Never intensify: ``` inst obj C1 413476.4 413317.0 413618.9 C2 161968.6 161940.7 162009.7 R1 473631.6 473161.8 474195.7 R2 276960.7 276735.0 277202.2 RC1 442861.8 442449.7 443491.5 RC2 232205.0 232028.2 232422.5 iters C1 155327.1 141096.9 161388.9 C2 186431.3 164638.5 196707.7 R1 95254.8 90775.0 99113.1 R2 80365.8 71534.8 85950.6 RC1 114015.4 105466.9 122114.0 RC2 90840.8 81770.4 97357.8 ``` Current (15%): ``` mean min max inst obj C1 413508.7 413262.9 413690.7 C2 161899.1 161878.3 161919.7 R1 473244.7 472820.1 474150.6 R2 277035.6 276801.2 277295.6 RC1 442598.2 442179.3 443196.9 RC2 232231.6 231965.8 232415.0 iters C1 125830.8 98592.9 139190.9 C2 147227.0 111460.5 167825.8 R1 70815.6 53593.1 87463.3 R2 60154.5 45681.5 66854.4 RC1 82952.4 62972.9 92364.6 RC2 67123.0 53691.6 74584.6 ``` Always intensify: ``` mean min max inst obj C1 413505.4 413221.1 413675.2 C2 161899.1 161875.0 161913.2 R1 473185.8 472940.9 473516.8 R2 277338.1 277084.1 277529.9 RC1 442229.6 441905.1 442437.5 RC2 232349.2 232158.3 232575.3 iters C1 91622.2 81969.1 98671.2 C2 92871.3 88609.6 100048.6 R1 33942.4 31362.4 36365.8 R2 31739.1 28063.3 34046.3 RC1 41675.0 36387.6 47300.1 RC2 35807.8 33177.4 39396.4 ```

[leonlan]

Intensification probability was added in HGS-DIMACS and did not exist in HGS-CVRP. @wouterkool do you have any results on this from DIMACS? Otherwise I suggest that we run a benchmark to figure out.

[leonlan]

I'm running a benchmark with 50% and 100% intensification probabilities.

Related: the intensification probability should be an argument of LocalSearch instead of GeneticAlgorithm. GA should only know about an "Educator" that improves the offspring, and if needed, also repairs the offspring.

[N-Wouda]

Related: the intensification probability should be an argument of LocalSearch instead of GeneticAlgorithm. GA should only know about an "Educator" that improves the offspring, and if needed, also repairs the offspring.

Agree, if we keep it. I'm strongly in favour of removing this, and think the only argument against removal would be if 100% turns out to be meaningfully worse than what we have now.

[wouterkool]

I don't remember how much difference it made, but it made some difference for some types of instances as we used different parameters for different instances in the final version. To me, it makes sense to intensify occasionally, but not always and I don't see so much downside from having it. If we want to have the simplest possible implementation, then sure we could remove it, however if we want to give the user some easy ways of customizing the behaviour of the algorithm then it may be actually useful to have something like this parameterizable.

[wouterkool]

If we want the code to be generally useful, I don't think we should make decisions solely based on performance on GH cases, but we should also support functionality that is or could be generally useful, if it is not unnecessarily complicated, which I think is the case for probabilistic intensification.

[leonlan]

GH1000, 10 seeds, 3600s

---

Main, default config

cost
min     33341.5
mean    33359.6
max     33374.5

iters
mean    114732

Main, 50% intensification probability

cost
min     33346.9
mean    33362.1
max     33378.0

iters
mean     90591

Main, 100% intensification probability

cost
min     33360.5
mean    33374.5
max     33387.4

iters
mean      73340

---

Having 100% intensification probability is about 0.05% worse than having 15% intensification probability. It's a small difference. My hypothesis here is that having 100% intensification on itself is not much worse, but it leads to less restarts.

[leonlan]

If we want the code to be generally useful, I don't think we should make decisions solely based on performance on GH cases, but we should also support functionality that is or could be generally useful, if it is not unnecessarily complicated, which I think is the case for probabilistic intensification.

I do agree with this. It may be worse/better for instances other than GH. Intensification probability is not a very difficult concept and providing this flexibility may pay off in terms of performance.

[N-Wouda]

I personally disagree. We've seen on the EURO/NeurIPS instances that there was no benefit from having this parameter, and here again the benefit is questionable at best. Some better caching of the route operators and a few more iterations would completely close the 100% vs 15% gap. The two intensification parameters we have now only add to the tuning burden, for no clear benefit, and that's doing our users a disservice by having them tune parameters that do not seem to matter.

[wouterkool]

I think you're jumping to conclusions on the basis of a single number (or 2 single numbers but I don't think EURO-NeurIPS is representative as those instances were rather small). From my experience, it differs a lot by the characteristics of the instance, which wildly vary for different instances in the GH benchmark. The user may have instances for which intensification does or does not make sense. I think functionally always/never/sometimes intensifying makes a lot of difference to the algorithm, and the fact that the resulting differences are small in this single number does not mean this flexibility is useless in general. @leonlan can we somewhere see the results for different instances or instance groups (C, RC and R 1 and 2, or the slightly different categorization we used at DIMACS)?

[leonlan]

Means per category. I don't know how to easily reproduce the categorization of DIMACS. There's almost no difference, and the small differences can be explained due to the variance (which is generally larger for the 100% intensify case).

category	main	50% intensify	100% intensify
C1	41355	41363	41373
C2	16187	16188	16191
R1	47376	47364	47377
R2	27709	27729	27767
RC1	44320	44305	44316
RC2	23211	23224	23224

We've seen on the EURO/NeurIPS instances that there was no benefit from having this parameter, and here again the benefit is questionable at best.

I only recall that there was no benefit in having intensfication at all (only on best), which would actually strengthen the case for keeping the intensification probability parameter to turn off intensification.

[N-Wouda]

(which is generally larger for the 100% intensify case).

Is that caused by the fewer iterations 100% intensify has? That'd make sense.

I only recall that there was no benefit in having intensfication at all

I tested this fairly early on, but I'd have to look back pretty far to find the results. One sec. EDIT: nope can't find it anymore.

which would actually strengthen the case for keeping the intensification probability parameter.

Or being able to turn it on/off, as desired. We could support that pretty easily by making route operators optional. No operators then just does nothing. I think that'd also make sense as default behaviour for search(), not just for intensify(), rather than raising an error as they do now. No operators is weird, but not exceptional.

[N-Wouda]

Related: the intensification probability should be an argument of LocalSearch instead of GeneticAlgorithm. GA should only know about an "Educator" that improves the offspring, and if needed, also repairs the offspring.

I've started working on the Educator stuff because I want to slowly pave the way towards a variable neighbourhood descent type educator. This is an issue for other educators. Additionally, we need to think about the overlap tolerance. Both of those arguments are LS-specific things that currently bleed over into the GA. I think the best idea is to move them into the (Python-side) LS.