jsprit/jsprit — pull request #82 by pierredavidbelanger (2014-02-24 21:36:01+00:00)
Title: SchrimpfAcceptance unit tests

This is more to initiate a talk about my prematureTermination problem rather than a real PR.

Not long ago we talk by email about a problem I have with the premature termination feature.

Here is what I do in my (groovy) code:

```
def algorithm = new SchrimpfFactory().createAlgorithm(problem)
algorithm.nuOfIterations = 10000
algorithm.prematureAlgorithmTermination = new IterationWithoutImprovementTermination(1000)
```

Whatever the algorithm do, it always ends at iteration `10000`.

I dig into this problem, and found the reason:

The `IterationWithoutImprovementTermination` uses the `DiscoveredSolution.accepted` field to determine how many `iterationsWithoutImprovement` have passed.

The problem with my code is that `DiscoveredSolution.accepted` is always `true`, so `iterationsWithoutImprovement` never increments.

I dig a little deeper and found that in my setup, it is the `SchrimpfAcceptance` that is responsible to accept new solution.

I discover two things about `SchrimpfAcceptance`:

- if during its warmup the `initialThreshold` is found to be `0.0`, my problem can not be reproduced.

- but if the `initialThreshold` is found to be a positive number during the warmup, `SchrimpfAcceptance` become too permissive.

I wrote some unit tests that demonstrate exactly this behaviour in this PR.

For example, it accepts the `newSolution` even if `newSolution`'s `cost` is equal to the `worst`'s `cost`, and this is exactly my case: the solution improve in the first 100 iterations, but all the 9900 others, the costs are the same, but `SchrimpfAcceptance` do not reject the new identical solutions.

Even if I can explain my problem, I may be wrong here since I do not know the theory behind the Schrimpf algorithm. Please correct me if I am wrong.

But if I am not wrong, here is the fix:

I think this line:
that https://github.com/pierredavidbelanger/jsprit/blob/master/jsprit-core/src/main/java/jsprit/core/algorithm/acceptor/SchrimpfAcceptance.java#L80

should be:

`if(newSolution.getCost() + threshold < worst.getCost())`

You can find this fix here:
https://github.com/pierredavidbelanger/jsprit/tree/schrimpf-acceptance-threshold-fix