Repository: PyVRP/PyVRP (python)

Issue:
Do we need probabilistic intensification?
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.

<details>

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
```


</details>


Pull request:
Remove intensify_on_best and intensify_probability
See the benchmarks in #170 for details. This PR:

- [x] Closes #170.
- [ ] Adds and passes relevant tests.
- [x] Has well-formatted code and documentation.

<details>

**Notes**:

- It is essential that you add a test when making code changes.
  This keeps the code coverage level up, and helps ensure the changes work as intended.
- When fixing a bug, you must add a test that would produce the bug in the master branch, and then show that it is fixed with the new code. 
- New code additions must be well formatted. Changes should pass the pre-commit workflow, which you can set up locally using [pre-commit](https://pre-commit.com/#intro). 
- Docstring additions must render correctly, including escapes and LaTeX.

</details>


Patch:
diff --git a/configs/cvrp.toml b/configs/cvrp.toml
index cc59cce..126a454 100644
--- a/configs/cvrp.toml
+++ b/configs/cvrp.toml
@@ -21,8 +21,6 @@ route_ops = [
 
 [genetic]
 repair_probability = 0.50
-intensify_probability = 1.00
-intensify_on_best = false
 nb_iter_no_improvement = 20_000
 
 
diff --git a/configs/vrptw.toml b/configs/vrptw.toml
index 153d9ed..1e3ff9f 100644
--- a/configs/vrptw.toml
+++ b/configs/vrptw.toml
@@ -21,8 +21,6 @@ route_ops = [
 
 [genetic]
 repair_probability = 0.80
-intensify_probability = 0.15
-intensify_on_best = true
 nb_iter_no_improvement = 20_000
 
 
diff --git a/pyvrp/GeneticAlgorithm.py b/pyvrp/GeneticAlgorithm.py
index 0e72857..acec12c 100644
--- a/pyvrp/GeneticAlgorithm.py
+++ b/pyvrp/GeneticAlgorithm.py
@@ -24,17 +24,12 @@ if TYPE_CHECKING:
 @dataclass
 class GeneticAlgorithmParams:
     repair_probability: float = 0.80
-    intensify_probability: float = 0.15
-    intensify_on_best: bool = True
     nb_iter_no_improvement: int = 20_000
 
     def __post_init__(self):
         if not 0 <= self.repair_probability <= 1:
             raise ValueError("repair_probability must be in [0, 1].")
 
-        if not 0 <= self.intensify_probability <= 1:
-            raise ValueError("intensify_probability must be in [0, 1].")
-
         if self.nb_iter_no_improvement < 0:
             raise ValueError("nb_iter_no_improvement < 0 not understood.")
 
@@ -163,49 +158,22 @@ class GeneticAlgorithm:
             self._pm.register_load_feasible(not sol.has_excess_load())
             self._pm.register_time_feasible(not sol.has_time_warp())
 
-        intensify_prob = self._params.intensify_probability
-        should_intensify = self._rng.rand() < intensify_prob
-
-        sol = self._ls.run(sol, self._cost_evaluator, should_intensify)
+        sol = self._ls.run(sol, self._cost_evaluator)
+        add_and_register(sol)
 
         if is_new_best(sol):
             self._best = sol
 
-            # Only intensify feasible, new best solutions. See also the repair
-            # step below. TODO Refactor to on_best callback (see issue #111)
-            if self._params.intensify_on_best:
-                sol = self._ls.intensify(
-                    sol, self._cost_evaluator, overlap_tolerance_degrees=360
-                )
-
-                if is_new_best(sol):
-                    self._best = sol
-
-        add_and_register(sol)
-
         # Possibly repair if current solution is infeasible. In that case, we
         # penalise infeasibility more using a penalty booster.
         if (
             not sol.is_feasible()
             and self._rng.rand() < self._params.repair_probability
         ):
-            should_intensify = self._rng.rand() < intensify_prob
-            sol = self._ls.run(
-                sol, self._pm.get_booster_cost_evaluator(), should_intensify
-            )
-
-            if is_new_best(sol):
-                self._best = sol
-
-                if self._params.intensify_on_best:
-                    sol = self._ls.intensify(
-                        sol,
-                        self._pm.get_booster_cost_evaluator(),
-                        overlap_tolerance_degrees=360,
-                    )
-
-                    if is_new_best(sol):
-                        self._best = sol
+            sol = self._ls.run(sol, self._pm.get_booster_cost_evaluator())
 
             if sol.is_feasible():
                 add_and_register(sol)
+
+            if is_new_best(sol):
+                self._best = sol
diff --git a/pyvrp/search/LocalSearch.py b/pyvrp/search/LocalSearch.py
index 12a3188..a343cd4 100644
--- a/pyvrp/search/LocalSearch.py
+++ b/pyvrp/search/LocalSearch.py
@@ -80,14 +80,13 @@ class LocalSearch:
         self,
         solution: Solution,
         cost_evaluator: CostEvaluator,
-        should_intensify: bool,
     ) -> Solution:
         """
         This method uses the :meth:`~search` and :meth:`~intensify` methods to
         iteratively improve the given solution. First, :meth:`~search` is
-        applied. Thereafter, if ``should_intensify`` is true,
-        :meth:`~intensify` is applied. This process repeats until no further
-        improvements are found. Finally, the improved solution is returned.
+        applied. Thereafter, :meth:`~intensify` is applied. This repeats until
+        no further improvements are found. Finally, the improved solution is
+        returned.
 
         Parameters
         ----------
@@ -95,10 +94,6 @@ class LocalSearch:
             The solution to improve through local search.
         cost_evaluator
             Cost evaluator to use.
-        should_intensify
-            Whether to apply :meth:`~intensify`. Intensification can provide
-            much better solutions, but is computationally demanding. By default
-            intensification is applied.
 
         Returns
         -------
@@ -106,22 +101,16 @@ class LocalSearch:
             The improved solution. This is not the same object as the
             solution that was passed in.
         """
-        # HACK We keep searching and intensifying to mimic the local search
-        # implementation of HGS-CVRP and HGS-VRPTW
-        # TODO separate load/export solution from c++ implementation
-        # so we only need to do it once
+        # TODO separate load/export solution from C++ implementation
+        # so we only need to do it once.
         while True:
             solution = self.search(solution, cost_evaluator)
-
-            if not should_intensify:
-                return solution
+            cost = cost_evaluator.penalised_cost(solution)
 
             new_solution = self.intensify(solution, cost_evaluator)
-
-            current_cost = cost_evaluator.penalised_cost(solution)
             new_cost = cost_evaluator.penalised_cost(new_solution)
 
-            if new_cost < current_cost:
+            if new_cost < cost:
                 solution = new_solution
                 continue
 
@@ -135,7 +124,7 @@ class LocalSearch:
     ) -> Solution:
         """
         This method uses the intensifying route operators on this local search
-        object to improve the given solution. To limit the computation
+        object to improve the given solution. To limit the computational
         demands of intensification, the  ``overlap_tolerance_degrees`` argument
         can be used to limit the number of route pairs that are evaluated.
 


Test patch:
diff --git a/pyvrp/tests/test_GeneticAlgorithm.py b/pyvrp/tests/test_GeneticAlgorithm.py
index 3a4ba0b..b0b4d87 100644
--- a/pyvrp/tests/test_GeneticAlgorithm.py
+++ b/pyvrp/tests/test_GeneticAlgorithm.py
@@ -18,69 +18,41 @@ from pyvrp.tests.helpers import make_random_solutions, read, read_solution
 
 
 @mark.parametrize(
-    "repair_probability,"
-    "intensify_probability,"
-    "intensify_on_best,"
-    "nb_iter_no_improvement",
+    "repair_probability, nb_iter_no_improvement",
     [
-        (-0.25, 0.5, True, 0),  # repair_probability < 0
-        (1.25, 0.5, True, 0),  # repair_probability > 1
-        (0.0, 0.5, True, -1),  # nb_iter_no_improvement < 0
-        (0.0, -0.25, True, 1),  # intensify_probability < 0
-        (0.0, 1.25, True, 1),  # intensify_probability > 1
+        (-0.25, 0),  # repair_probability < 0
+        (1.25, 0),  # repair_probability > 1
+        (0.0, -1),  # nb_iter_no_improvement < 0
     ],
 )
-def test_params_constructor_throws_when_arguments_invalid(
+def test_params_constructor_raises_when_arguments_invalid(
     repair_probability: float,
-    intensify_probability: int,
-    intensify_on_best: bool,
     nb_iter_no_improvement: int,
 ):
     """
     Tests that invalid configurations are not accepted.
     """
     with assert_raises(ValueError):
-        GeneticAlgorithmParams(
-            repair_probability,
-            intensify_probability,
-            intensify_on_best,
-            nb_iter_no_improvement,
-        )
+        GeneticAlgorithmParams(repair_probability, nb_iter_no_improvement)
 
 
 @mark.parametrize(
-    "repair_probability,"
-    "intensify_probability,"
-    "intensify_on_best,"
-    "nb_iter_no_improvement",
+    "repair_probability, nb_iter_no_improvement",
     [
-        (0.0, 0.5, True, 0),  # nb_iter_no_improvement == 0
-        (0.0, 0.5, True, 1),  # repair_probability == 0
-        (1.0, 0.5, True, 1),  # repair_probability == 1
-        (0.5, 0, True, 1),  # intensify_probability == 0
-        (0.5, 1, True, 1),  # intensify_probability == 1
-        (0.5, 0.5, False, 1),  # intensify_on_best is False
+        (0.0, 0),  # nb_iter_no_improvement == 0
+        (0.0, 1),  # repair_probability == 0
+        (1.0, 1),  # repair_probability == 1
     ],
 )
 def test_params_constructor_does_not_raise_when_arguments_valid(
     repair_probability: float,
-    intensify_probability: float,
-    intensify_on_best: bool,
     nb_iter_no_improvement: int,
 ):
     """
     Tests valid boundary cases.
     """
-    params = GeneticAlgorithmParams(
-        repair_probability,
-        intensify_probability,
-        intensify_on_best,
-        nb_iter_no_improvement,
-    )
-
+    params = GeneticAlgorithmParams(repair_probability, nb_iter_no_improvement)
     assert_allclose(params.repair_probability, repair_probability)
-    assert_equal(params.intensify_probability, intensify_probability)
-    assert_equal(params.intensify_on_best, intensify_on_best)
     assert_equal(params.nb_iter_no_improvement, nb_iter_no_improvement)
 
 
@@ -148,8 +120,6 @@ def test_initial_solutions_added_when_restarting():
 
     params = GeneticAlgorithmParams(
         repair_probability=0,
-        intensify_probability=0,
-        intensify_on_best=False,
         nb_iter_no_improvement=100,
     )
     algo = GeneticAlgorithm(data, pm, rng, pop, ls, srex, init, params=params)
@@ -177,12 +147,7 @@ def test_best_solution_improves_with_more_iterations():
     ls = LocalSearch(data, rng, compute_neighbours(data))
     ls.add_node_operator(Exchange10(data))
 
-    ga_params = GeneticAlgorithmParams(
-        intensify_probability=0, intensify_on_best=False
-    )
-    algo = GeneticAlgorithm(
-        data, pm, rng, pop, ls, srex, init, params=ga_params
-    )
+    algo = GeneticAlgorithm(data, pm, rng, pop, ls, srex, init)
 
     initial_best = algo.run(MaxIterations(0)).best
     new_best = algo.run(MaxIterations(25)).best