Score corruption with PlanningListVariable with Shadow variables on the nested planning entity

[Inlustra]

Hi guys,

Currently trying to solve an issue where, in FULL_ASSERT mode, we clearly have something going awry.
Brief description of the problem: VRPTW (Techincally it's moving vehicles, so in this model, our driver becomes the moving object or vehicle)

We have a score corruption for almost all of the constraint providers and I'm not sure why, it mostly looks like it's working ok in non-full-assert mode.

Definitely not looking for a handout here, despite the wall of code. Rather, trying to understand if PlanningListVariables support this use-case?

Some are in Excess and some are missing.

Score corruption analysis:
  The working scoreDirector has 1 ConstraintMatch(s) which are in excess (and should not be there):
    .../MINUTES_FROM_DRIVER_HOME/[TripAssignment@54cc5eb, .LocationLookupCache@421bc991]=0hard/0medium/-63soft
  The working scoreDirector has 3 ConstraintMatch(s) which are missing:
   .../MINUTES_BETWEEN_ASSIGNMENTS/[TripAssignment@54cc5eb]=0hard/0medium/-31soft

An example constraint:

    private fun missingWindow(factory: ConstraintFactory): Constraint {
        return factory.forEach(TripAssignment::class.java)
                .filter { assignment ->
                    assignment.driver != null &&
                            assignment.withinTimeWindow != null &&
                            !assignment.withinTimeWindow!!
                }
                .penalizeConfigurable()
                .asConstraint(VehicleDeliveryConstraint.MISSING_WINDOW.name)
    }

I have the following DriverTripSchedule:

@PlanningEntity
class DriverTripSchedule : LocationAware {
    var driver: Driver
... Constructors etc.

    @PlanningListVariable(valueRangeProviderRefs = ["tripAssignments"])
    var tripAssignments: List<TripAssignment> = emptyList()
...
}

And the TripAssignment which is made up of many shadow variables:

@PlanningEntity(difficultyComparatorClass = TripAssignmentDifficultyComparator::class)
public class TripAssignment : LocationAware {

        var trip: Trip? = null

        @get:ShadowVariable(
                        sourceVariableName = "previousTripAssignment",
                        variableListenerClass = DriverUpdatingVariableListener::class
        )
        var previousLocation: Location? = null

         /////////////// ... There are many other piggy back shadow variables here.
        /////////////// ... setOffTime, pickupTime, waitTime, dropoffTime... etc

        @get:PiggybackShadowVariable(
                        shadowVariableName = "previousLocation",
        )
        var distanceToTimeWindowMinutes: Int? = null

        @get:PreviousElementShadowVariable(sourceVariableName = "tripAssignments")
        var previousTripAssignment: TripAssignment? = null

        @get:NextElementShadowVariable(sourceVariableName = "tripAssignments")
        var nextTripAssignment: TripAssignment? = null

        @get:InverseRelationShadowVariable(sourceVariableName = "tripAssignments")
        var driver: DriverTripSchedule? = null

Finally the listener itself, this is pretty large, as such I didn't want to provide the whole thing:

class DriverUpdatingVariableListener : VariableListener<VehicleDeliverySolution, TripAssignment>

However, some small examples, we're definitely calling the variable changes using the following

        private fun setWithinTimeWindow(
                        scoreDirector: ScoreDirector<VehicleDeliverySolution>,
                        assignment: TripAssignment,
                        withinTimeWindow: Boolean?
        ) {
                scoreDirector.beforeVariableChanged(assignment, "withinTimeWindow")
                assignment.withinTimeWindow = withinTimeWindow
                scoreDirector.afterVariableChanged(assignment, "withinTimeWindow")
        }

with the all of the logic happening inside afterVariableChanged

override fun afterVariableChanged(
                        scoreDirector: ScoreDirector<VehicleDeliverySolution>,
                        assignment: TripAssignment
        ) {
                val previousLocation = calculatePreviousLocation(scoreDirector, assignment)
                setPreviousLocation(scoreDirector, assignment, previousLocation)

                val setOffTime = calculateSetOffTime(scoreDirector, assignment)
                setSetOffTime(scoreDirector, assignment, setOffTime)

               ... etc
        }

Could anyone point me towards anything that I could be doing wrong here?
It mentions Shadow variable corruption in the working scoreDirector as none:

    app.rowm.eden.solver/MISSING_WINDOW/[app.rowm.eden.domain.solution.TripAssignment@2170523]=0hard/-1medium/0soft
  Maybe there is a bug in the score constraints of those ConstraintMatch(s).
  Maybe a score constraint doesn't select all the entities it depends on, but finds some through a reference in a selected entity. This corrupts incremental score calculation, because the constraint is not re-evaluated if such a non-selected entity changes.
Shadow variable corruption in the working scoreDirector:
  None
        at ai.timefold.solver.core.impl.score.director.AbstractScoreDirector.assertScoreFromScratch(AbstractScoreDirector.java:638)

[triceo]

Hello there,

First of all, have you tried the recently released Timefold Solver 1.1.0? We have changed a lot of the CS internals there to address a nasty bug and there is a decent chance that your problem is already solved.

If the issue persists even in 1.1.0, let's keep looking further.

[triceo]

Here's the thing:

forEach(Entity.class)
    .filter(entity -> entity.otherEntity.something ... )

Is only going to trigger when an Entity instance changes.
This is not a problem if the only thing you're ever doing is checking if entity.otherEntity is null; because entity has that information.
However, when otherEntity changes and you transitively depend on its contents, you got yourself an instant score corruption.

Compare to this:

forEach(Entity.class)
    .join(OtherEntity.class,
         equals(Entity::getOtherEntity, Function.identity())

This is going to trigger both when Entity changes and OtherEntity changes, therefore solving the transitive score corruption.

[Inlustra]

That has definitely got me thinking though.

Should the following become:

        @get:ShadowVariable(
                        sourceVariableName = "previousTripAssignment",
                        variableListenerClass = DriverUpdatingVariableListener::class
        )
        var previousLocation: Location? = null

        @get:ShadowVariable(
                        sourceVariableName = "driver",
                        variableListenerClass = DriverUpdatingVariableListener::class
        )
        @get:ShadowVariable(
                        sourceVariableName = "previousTripAssignment",
                        variableListenerClass = DriverUpdatingVariableListener::class
        )
        var previousLocation: Location? = null

Giving this a quick test, I get entirely new errors 😓

java.lang.IllegalStateException: UndoMove corruption (-1medium): the beforeMoveScore (-23init/0hard/0medium/0soft) is not the undoScore (-23init/0hard/-1medium/0soft) which is the uncorruptedScore (-23init/0hard/-1medium/0soft) of the workingSolution.

Also bit of a side note, I get this issue removing the entire localSearch section of the configuration.xml, so my assumption then is that it's not related to the type of move?

Edit:

Riiiight, thank you for your explanation, I'll give that a go.

[triceo]

If you get the same issues without local search (so using only CH), then yes, the issue is likely limited to Constraint Streams.

Or perhaps your variable listeners - implementing custom complex logic in there is error-prone and I recommend you test your variable listeners heavily, to make sure that they treat all corner cases correctly. It is very easy to corrupt your score by having an incorrect implementation of a variable listener.

[Inlustra]

I'm still seeing the exact same issue unfortunately, I'll get on testing the variable listener thoroughly.

Trying to narrow this down seems quite tough, I'll try to produce a minimal repro.
To confirm: PlanningListVariables + Shadow variables on the list entity, is supported? :)

Thanks again for all of your help!

[triceo]

Shadow variables on an entity should never be an issue.

Typically, there is a process to produce a minimal Timefold reproducer:

1. Remove all moves you don't need. If you see the issue in Construction Heuristics already, you're done.
2. Keep removing constraints until only one remains which still reproduces the issue. (Only very rarely it is a combination of several constraints.)
3. Minimize this one remaining constraint to not include joins and filters that aren't necessary to reproduce.
4. Move on to the domain. Keep removing entities and values until you have the minimum possible subset which still reproduces the issue.
5. At that point, it should be relatively easy to write a test that reproduces the issue; typically it is one or two entities, one or two values, and one or two change moves.
6. When you have the test, you can start looking into what went wrong. And maybe, at this point, you realize that your complex variable listener didn't cover a corner case well.
7. And if the issue still prevails, then that's the point where you call Timefold support. :-)

[Inlustra]

Just wanted to comment back here that it was indeed a subtle bug in a listener! We ended up migrating to a list variable listener and testing the bejeezus out of that which is where we saw the bug!

Massive thank you to @triceo 🙏

[triceo]

@Inlustra Happy to help. You're not the first who struggled with complex logic in variable listeners; we're investigating options of making that whole area simpler to work with, but it may be a while before something materializes; assuming we can even come up with something better that still works.