The CH phase requires a very long time to complete, is there a method to improvement it ?

[kentbill]

I have a dataset to solver that uses PlanningListVariable. The number of planning entities is quite large, such as over 5000, and the CH phase getting slower and slower. The number of moves per step is about between 10 and 60. When more than 2000 steps are completed, it even takes a few seconds to complete one step. Is there any way to shorten it?

[Christopher-Chianelli]

Greetings @kentbill ! Without seeing your domain and constraints, I cannot give specific advice. But since only 10-60 moves are evaluated per step, I suspect you have a large cross product in the join of one of your constraints. Try using Joiners where possible, and do filtering before the join where possible. For example,

constraintFactory.forEach(Visit.class)
    .join(Visit.class)
    .filter((a,b) -> b.getVisitType() == VisitType.PRIORITY)
    .filter((a, b) -> a.getArrivalTime().isBefore(b.getArrivalTime())
    .filter((a, b) -> a.getPriority() < b.getPriority())
    .filter((a,b) -> Objects.equal(a.getVehicle(), b.getVehicle()) )
    .penalize(HardSoftScore.ONE_HARD)
    .asConstraint("...")

can be rewritten as

constraintFactory.forEach(Visit.class)
    .join(constraintFactory.forEach(Visit.class).filter(b ->  b.getVisitType() == VisitType.PRIORITY),
             Joiners.lessThan(Visit::getArrivalTime),
             Joiners.lessThan(Visit::getPriority),
             Joiners.equal(Visit::getVehicle)
    )
    .penalize(HardSoftScore.ONE_HARD)
    .asConstraint("...")

For other performance tips, see https://docs.timefold.ai/timefold-solver/latest/constraints-and-score/performance

[kentbill]

Thank you! @Christopher-Chianelli

[PatrickDiallo23]

Another underrated advice is to improve the score calculation speed. A way to do that is to use the object identifier rather than use the whole object when you are using Joiners (and Joiners.equal)

[kentbill]

Thank you, @PatrickDiallo23

Is that so? A Joiner uses the entire object, isn't it actually using pointer to the object? Will this consume more computation time than using object identifier?

[PatrickDiallo23]

From what I saw, it is extracting the objects from Joiner.equal(), then it uses Object.equals() and hashCode() that is defined in your entities or planning variables (correct me if I am wrong). From my point of view, if you already know what you need to compare (and you always expect to be same object), it is (way) faster to do a shortcut and just compare the ids that are, in most cases, primitives, and thus they can be compared via == (again, correct me if I’m wrong). In my case, I observed a great performance increase.

Another perspective that can be useful is that the constraints are inspired from streams (Java streams) and sql queries. So, if you know how to optimize in those 2 worlds, then you can improve CH easily.

[triceo]

I think you can have your equals, and don't need to extract the ID.

If you already have the ID, and the ID uniquely describes the object, then you can have equals only contain the ID check.
If your object doesn't have the ID, then there is nothing to extract and you need to do the whole equals anyway.