6.9. Termination

Not all phases terminate automatically and sometimes you don't want to wait that long anyway. A Solver can be terminated synchronously by up-front configuration or asynchronously from another thread.
Especially metaheuristic phases will need to be told when to stop solving. This can be because of a number of reasons: the time is up, the perfect score has been reached, just before its solution is used, ... The only thing you can't depend on, is on finding the optimal solution (unless you know the optimal score), because a metaheuristic algorithm generally doesn't know it when it finds the optimal solution. For real-life problems this doesn't turn out to be much of a problem, because finding the optimal solution could take years, so you'll want to terminate sooner anyway. The only thing that matters is finding the best solution in the available time.
Important
If no termination is configured (and a metaheuristic algorithm is used), the Solver will run forever, until terminateEarly() is called from another thread. This is especially common during real-time planning.
For synchronous termination, configure a Termination on a Solver or a Phase when it needs to stop. You can implement your own Termination, but the built-in implementations should suffice for most needs. Every Termination can calculate a time gradient (needed for some optimization algorithms), which is a ratio between the time already spent solving and the estimated entire solving time of the Solver or Phase.

6.9.1. TimeMillisSpentTermination

Terminates when an amount of time has been used: 
  <termination>
    <millisecondsSpentLimit>500</millisecondsSpentLimit>
  </termination>
  <termination>
    <secondsSpentLimit>10</secondsSpentLimit>
  </termination>
  <termination>
    <minutesSpentLimit>5</minutesSpentLimit>
  </termination>
  <termination>
    <hoursSpentLimit>1</hoursSpentLimit>
  </termination>
  <termination>
    <daysSpentLimit>2</daysSpentLimit>
  </termination>
Multiple time types can be used together, for example to configure 150 minutes, either configure it directly: 
  <termination>
    <minutesSpentLimit>150</minutesSpentLimit>
  </termination>
Or use a combination that sums up to 150 minutes: 
  <termination>
    <hoursSpentLimit>2</hoursSpentLimit>
    <minutesSpentLimit>30</minutesSpentLimit>
  </termination>
Note
This Termination will most likely sacrifice perfect reproducibility (even with environmentMode REPRODUCIBLE) because the available CPU time differs frequently between runs:
  • The available CPU time influences the number of steps that can be taken, which might be a few more or less.
  • The Termination might produce slightly different time gradient values, which will send time gradient based algorithms (such as Simulated Annealing) on a radically different path.

6.9.2. UnimprovedTimeMillisSpentTermination

Terminates when the best score hasn't improved in an amount of time: 
  <localSearch>
    <termination>
      <unimprovedMillisecondsSpentLimit>500</unimprovedMillisecondsSpentLimit>
    </termination>
  </localSearch>
  <localSearch>
    <termination>
      <unimprovedSecondsSpentLimit>10</unimprovedSecondsSpentLimit>
    </termination>
  </localSearch>
  <localSearch>
    <termination>
      <unimprovedMinutesSpentLimit>5</unimprovedMinutesSpentLimit>
    </termination>
  </localSearch>
  <localSearch>
    <termination>
      <unimprovedHoursSpentLimit>1</unimprovedHoursSpentLimit>
    </termination>
  </localSearch>
  <localSearch>
    <termination>
      <unimprovedDaysSpentLimit>1</unimprovedDaysSpentLimit>
    </termination>
  </localSearch>
This termination should not be applied to Construction Heuristics, because they only update the best solution at the end. Therefore it might be better to configure it on a specific Phase (such as <localSearch>), instead of on the Solver itself.
Note
This Termination will most likely sacrifice perfect reproducibility (even with environmentMode REPRODUCIBLE) because the available CPU time differs frequently between runs:
  • The available CPU time influences the number of steps that can be taken, which might be a few more or less.
  • The Termination might produce slightly different time gradient values, which will send time gradient based algorithms (such as Simulated Annealing) on a radically different path.

6.9.3. BestScoreTermination

Terminates when a certain score has been reached. You can use this Termination if you know the perfect score, for example for 4 queens (which uses a SimpleScore): 
  <termination>
    <bestScoreLimit>0</bestScoreLimit>
  </termination>
For a planning problem with a HardSoftScore, it could look like this: 
  <termination>
    <bestScoreLimit>0hard/-5000soft</bestScoreLimit>
  </termination>
For a planning problem with a BendableScore with 3 hard levels and 1 soft level, it could look like this: 
  <termination>
    <bestScoreLimit>0/0/0/-5000</bestScoreLimit>
  </termination>
To terminate once a feasible solution has been reached, this Termination isn't practical because it requires a bestScoreLimit such as 0hard/-2147483648soft. Instead, use the next termination.

6.9.4. BestScoreFeasibleTermination

Terminates when a certain score is feasible. Requires that the Score implementation implements FeasibilityScore. 
  <termination>
    <bestScoreFeasible>true</bestScoreFeasible>
  </termination>
This Termination is usually combined with other terminations.

6.9.5. StepCountTermination

Terminates when an amount of steps has been reached: 
  <localSearch>
    <termination>
      <stepCountLimit>100</stepCountLimit>
    </termination>
  </localSearch>
This Termination can only be used for a Phase (such as <localSearch>), not for the Solver itself.

6.9.6. UnimprovedStepCountTermination

Terminates when the best score hasn't improved in a number of steps: 
  <localSearch>
    <termination>
      <unimprovedStepCountLimit>100</unimprovedStepCountLimit>
    </termination>
  </localSearch>
If the score hasn't improved recently, it's probably not going to improve soon anyway and it's not worth the effort to continue. We have observed that once a new best solution is found (even after a long time of no improvement on the best solution), the next few steps tend to improve the best solution too.
This Termination can only be used for a Phase (such as <localSearch>), not for the Solver itself.

6.9.7. Combining Multiple Terminations

Terminations can be combined, for example: terminate after 100 steps or if a score of 0 has been reached: 
  <termination>
    <terminationCompositionStyle>OR</terminationCompositionStyle>
    <stepCountLimit>100</stepCountLimit>
    <bestScoreLimit>0</bestScoreLimit>
  </termination>
Alternatively you can use AND, for example: terminate after reaching a feasible score of at least -100 and no improvements in 5 steps: 
  <termination>
    <terminationCompositionStyle>AND</terminationCompositionStyle>
    <unimprovedStepCountLimit>5</unimprovedStepCountLimit>
    <bestScoreLimit>-100</bestScoreLimit>
  </termination>
This example ensures it doesn't just terminate after finding a feasible solution, but also completes any obvious improvements on that solution before terminating.

6.9.8. Asynchronous Termination from Another Thread

Sometimes you'll want to terminate a Solver early from another thread, for example because a user action or a server restart. This cannot be configured by a Termination as it's impossible to predict when and if it will occur. Therefore the Solver interface has these 2 thread-safe methods: 
public interface Solver {

    // ...

    boolean terminateEarly();
    boolean isTerminateEarly();

}
If you call the terminateEarly() method from another thread, the Solver will terminate at its earliest convenience and the solve(Solution) method will return in the original Solver thread.