Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

fix: Ruin and Recreate index out of bound #1305

Closed
zepfred opened this issue Jan 6, 2025 · 3 comments · Fixed by #1320
Closed

fix: Ruin and Recreate index out of bound #1305

zepfred opened this issue Jan 6, 2025 · 3 comments · Fixed by #1320
Assignees
Labels
bug Something isn't working
Milestone

Comments

@zepfred
Copy link
Contributor

zepfred commented Jan 6, 2025

The score corruption occurs because the CH adds values to destination entities without recording a list change event beforehand. Let's assume the following example:

Before:
v1 -> c1 - c2 - c3
v2 -> c4

Ruined customers: 
c1 and c2

After:
v1 -> c3
v2 -> c4 - c1 - c2

Since only values from v1 are selected, the R&R move will record the before list change event only for v1, while erasing v2 as part of the rollback actions. We cannot predict which destination entities will be updated, which makes it difficult to record the necessary changes before the list is modified. The list R&R move is failing with the following:

2025-01-06 13:16:22,028 ERROR [org.acm.veh.res.VehicleRoutePlanResource] (pool-8-thread-1) Failed solving jobId (3ff26dab-05ae-4e47-af4d-53d671056ce9).: java.lang.IndexOutOfBoundsException: Index 8 out of bounds for length 2
        at java.base/jdk.internal.util.Preconditions.outOfBounds(Preconditions.java:100)
        at java.base/jdk.internal.util.Preconditions.outOfBoundsCheckIndex(Preconditions.java:106)
        at java.base/jdk.internal.util.Preconditions.checkIndex(Preconditions.java:302)
        at java.base/java.util.Objects.checkIndex(Objects.java:385)
        at java.base/java.util.ArrayList.remove(ArrayList.java:551)
        at ai.timefold.solver.core.impl.domain.variable.descriptor.ListVariableDescriptor.removeElement(ListVariableDescriptor.java:158)
        at ai.timefold.solver.core.impl.heuristic.selector.move.generic.list.ruin.ListRuinRecreateMove.doMoveOnGenuineVariables(ListRuinRecreateMove.java:67)
        at ai.timefold.solver.core.impl.heuristic.move.AbstractMove.doMoveOnly(AbstractMove.java:26)
        at ai.timefold.solver.core.impl.heuristic.move.LegacyMoveAdapter.execute(LegacyMoveAdapter.java:54)
        at ai.timefold.solver.core.impl.score.director.AbstractScoreDirector.doAndProcessMove(AbstractScoreDirector.java:265)
        at ai.timefold.solver.core.impl.localsearch.decider.LocalSearchDecider.doMove(LocalSearchDecider.java:123)
        at ai.timefold.solver.core.impl.localsearch.decider.LocalSearchDecider.decideNextStep(LocalSearchDecider.java:101)
        at ai.timefold.solver.core.impl.localsearch.DefaultLocalSearchPhase.solve(DefaultLocalSearchPhase.java:71)
        at ai.timefold.solver.core.impl.solver.AbstractSolver.runPhases(AbstractSolver.java:83)
        at ai.timefold.solver.core.impl.solver.DefaultSolver.solve(DefaultSolver.java:197)
        at ai.timefold.solver.core.impl.solver.DefaultSolverJob.call(DefaultSolverJob.java:125)
        at java.base/java.util.concurrent.FutureTask.run(FutureTask.java:317)
        at java.base/java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1144)
        at java.base/java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:642)
        at java.base/java.lang.Thread.run(Thread.java:1583)
        Suppressed: java.lang.IllegalStateException: workingInitScore > 0 (1).
Maybe a custom move is removing more entities than were ever added?

                at ai.timefold.solver.core.impl.score.director.AbstractScoreDirector.assertInitScoreZeroOrLess(AbstractScoreDirector.java:255)
                at ai.timefold.solver.core.impl.score.director.AbstractScoreDirector.afterListVariableElementAssigned(AbstractScoreDirector.java:429)
                at ai.timefold.solver.core.impl.move.director.ListVariableBeforeUnassignmentAction.undo(ListVariableBeforeUnassignmentAction.java:12)
                at ai.timefold.solver.core.impl.move.director.VariableChangeRecordingScoreDirector.undoChanges(VariableChangeRecordingScoreDirector.java:64)
                at ai.timefold.solver.core.impl.move.director.EphemeralMoveDirector.close(EphemeralMoveDirector.java:47)
                at ai.timefold.solver.core.impl.score.director.AbstractScoreDirector.doAndProcessMove(AbstractScoreDirector.java:264)
                ... 10 more

@zepfred zepfred self-assigned this Jan 6, 2025
@zepfred zepfred added the bug Something isn't working label Jan 6, 2025
@zepfred zepfred changed the title fix: List Ruin and Recreate index out of bound fix: Ruin and Recreate index out of bound Jan 6, 2025
@triceo
Copy link
Contributor

triceo commented Jan 6, 2025

@zepfred FYI we recently noticed a score corruption in R&R. Very well may be a symptom of the same problem. Please talk to @Christopher-Chianelli, he investigated it and may be on his way to fix it - more importantly, let's not have two people working on possibly the same thing.

@zepfred
Copy link
Contributor Author

zepfred commented Jan 6, 2025

@zepfred FYI we recently noticed a score corruption in R&R. Very well may be a symptom of the same problem. Please talk to @Christopher-Chianelli, he investigated it and may be on his way to fix it - more importantly, let's not have two people working on possibly the same thing.

It is indeed a case of score corruption. Thank you for letting me know.

@zepfred
Copy link
Contributor Author

zepfred commented Jan 6, 2025

Regression introduced by 30c97c5

@zepfred zepfred linked a pull request Jan 8, 2025 that will close this issue
@triceo triceo added this to the v1.18.0 milestone Jan 15, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working
Projects
None yet
2 participants