Uploaded image for project: 'OptaPlanner'
  1. OptaPlanner
  2. PLANNER-283

Phase termination by timeout can cause incremental vs easy score assertion to fail

    XMLWordPrintable

Details

    • Bug
    • Resolution: Unresolved
    • Major
    • Future
    • 6.1.0.Final
    • optaplanner-core

    Description

      I am modelling a VRP with chained variables. I am using an incremental score calculator and I am using an easy score calculator to check it with assertions. The assertion passes during the search (meaning the scores stay in sync), except from at the point of solver termination. It has taken me a while to piece together the cause of this, but I think it is as described below.

      In the class AcceptedForager, if the first move that is added (via addMove() - line 93) is not accepted then that move gets added to maxScoreUnacceptedList (line 101). This happens with all subsequent unaccepted moves (replacing the one on the maxScoreUnacceptedList) until the first accepted move is found, at which stage acceptedMoveCount is > 0 so line 101 is no longer executed.

      At the point of termination via timeout, the LocalSearchDecider can break out of the move assessment loop before a move has been accepted (line 127 of LocalSearchDecider). After breaking out of the move assessment, the LocalSearchDecider calls forager.pickMove() on line 131.

      Inside AcceptedForager, pickMove() calls pickMaxScoreMoveScope() to get the best move. If there are no accepted moves (which can be the case when terminated by timeout) then the AcceptedForager falls back to returning the move on the maxScoreUnacceptedList.

      This usually has an old move on it, from the very start of the search as described above. The score associated with this old move is no longer correct as the model has changed substantially since that move was assessed.

      This causes assertWorkingScoreFromScratch to fail inside the doStep() method of DefaultLocalSearchPhase.

      It seems that DefaultLocalSearchPhase line 67-71 assumes that the step will be null if the phase has been terminated, but in fact this is not the case. The step is not null because of the old step hanging around on the unaccepted list of the AcceptedForager.

      Not sure about a fix, but one option would be to return on line 127 of LocalSearchDecider instead of just breaking.

      Attachments

        Activity

          People

            Unassigned Unassigned
            andrew.bone Andrew Bone (Inactive)
            Votes:
            0 Vote for this issue
            Watchers:
            1 Start watching this issue

            Dates

              Created:
              Updated: