Optaplanner - ConstructionHeuristics find a feasible solution before all planning entity get initialized

Question

I have this setting:

%test.quarkus.optaplanner.solver.termination.best-score-limit=0hard/*soft

In ConstructionHeuristics phase, if optaplanner get a 0 HARD score (feasible solution) before assigning all planning entities an initial value, then it becomes infeasible again (-1 HARD) after assigning more planning entities initial value, I noticed when the construction heuristics phase ends, optaplanner will not do LOCAL SEARCH and just report the infeasible solution as final best solution.

Shouldn't the final best solution be the one after all planning entities got assigned a value and starts from there to check whether to terminate the search?

I even have hard constraints to not allow any Planning entities to have null planning variable. but before the planning entity got initialized in Construction Heuristics phase, the hard constraint does not seem to kick in.

Is there a way to add a constraint for uninitialized planning entity? How to let optaplanner to take the final best solution only after all planning entities are initialized?

Here are the logs I see in my case:

2022-02-09 14:20:05,126 INFO  [org.opt.cor.imp.sol.DefaultSolver] (pool-9-thread-1) Solving started: time spent (90), best score (-30init/0hard/0soft), environment mode (REPRODUCIBLE), move thread count (NONE), random (JDK with seed 0).
2022-02-09 14:20:05,198 DEBUG [org.opt.cor.imp.con.DefaultConstructionHeuristicPhase] (pool-9-thread-1)     CH step (0), time spent (170), score (-28init/-2hard/-5soft), selected move count (32), picked move ([a.0 {null -> MANUAL_ASSEMBLY}, a.0 {null -> Inve.0/0-0}]).
2022-02-09 14:20:05,247 DEBUG [org.opt.cor.imp.con.DefaultConstructionHeuristicPhase] (pool-9-thread-1)     CH step (1), time spent (219), score (-26init/-1hard/-5soft), selected move count (33), picked move ([f.4 {null -> MANUAL_ASSEMBLY}, f.4 {null -> Inve.0/0-0}]).
2022-02-09 14:20:05,286 DEBUG [org.opt.cor.imp.con.DefaultConstructionHeuristicPhase] (pool-9-thread-1)     CH step (2), time spent (258), score (-24init/-1hard/-5soft), selected move count (34), picked move ([2.f {null -> MANUAL_ASSEMBLY}, 2.f {null -> Inve.0/0-0}]).
2022-02-09 14:20:05,315 DEBUG [org.opt.cor.imp.con.DefaultConstructionHeuristicPhase] (pool-9-thread-1)     CH step (3), time spent (287), score (-22init/-1hard/-4soft), selected move count (35), picked move ([9.8 {null -> MANUAL_ASSEMBLY}, 9.8 {null -> Inve.0/0-0}]).
2022-02-09 14:20:05,338 DEBUG [org.opt.cor.imp.con.DefaultConstructionHeuristicPhase] (pool-9-thread-1)     CH step (4), time spent (310), score (-20init/-1hard/-4soft), selected move count (36), picked move ([6.c {null -> MANUAL_ASSEMBLY}, 6.c {null -> Inve.0/0-0}]).
2022-02-09 14:20:05,362 DEBUG [org.opt.cor.imp.con.DefaultConstructionHeuristicPhase] (pool-9-thread-1)     CH step (5), time spent (334), score (-18init/-1hard/-4soft), selected move count (37), picked move ([8.3 {null -> MANUAL_ASSEMBLY}, 8.3 {null -> Inve.0/0-0}]).
2022-02-09 14:20:05,384 DEBUG [org.opt.cor.imp.con.DefaultConstructionHeuristicPhase] (pool-9-thread-1)     CH step (6), time spent (356), score (-16init/-1hard/-4soft), selected move count (38), picked move ([f.2 {null -> MANUAL_ASSEMBLY}, f.2 {null -> Inve.0/0-0}]).
2022-02-09 14:20:05,400 DEBUG [org.opt.cor.imp.con.DefaultConstructionHeuristicPhase] (pool-9-thread-1)     CH step (7), time spent (372), score (-14init/-1hard/-3soft), selected move count (39), picked move ([4.6 {null -> MANUAL_ASSEMBLY}, 4.6 {null -> Inve.0/0-0}]).
2022-02-09 14:20:05,415 DEBUG [org.opt.cor.imp.con.DefaultConstructionHeuristicPhase] (pool-9-thread-1)     CH step (8), time spent (387), score (-12init/-1hard/-3soft), selected move count (40), picked move ([8.2 {null -> MANUAL_ASSEMBLY}, 8.2 {null -> Inve.0/0-0}]).
2022-02-09 14:20:05,428 DEBUG [org.opt.cor.imp.con.DefaultConstructionHeuristicPhase] (pool-9-thread-1)     CH step (9), time spent (400), score (-10init/0hard/-3soft), selected move count (41), picked move ([a.4 {null -> MANUAL_ASSEMBLY}, a.4 {null -> Inve.0/0-0}]).
2022-02-09 14:20:05,440 DEBUG [org.opt.cor.imp.con.DefaultConstructionHeuristicPhase] (pool-9-thread-1)     CH step (10), time spent (412), score (-8init/0hard/-2soft), selected move count (42), picked move ([4.5 {null -> MANUAL_ASSEMBLY}, 4.5 {null -> Inve.0/0-0}]).
2022-02-09 14:20:05,453 DEBUG [org.opt.cor.imp.con.DefaultConstructionHeuristicPhase] (pool-9-thread-1)     CH step (11), time spent (425), score (-6init/0hard/-2soft), selected move count (43), picked move ([5.d {null -> MANUAL_ASSEMBLY}, 5.d {null -> Inve.0/0-0}]).
2022-02-09 14:20:05,474 DEBUG [org.opt.cor.imp.con.DefaultConstructionHeuristicPhase] (pool-9-thread-1)     CH step (12), time spent (446), score (-4init/0hard/-2soft), selected move count (44), picked move ([8.a {null -> MANUAL_ASSEMBLY}, 8.a {null -> Inve.0/0-0}]).
2022-02-09 14:20:05,501 DEBUG [org.opt.cor.imp.con.DefaultConstructionHeuristicPhase] (pool-9-thread-1)     CH step (13), time spent (473), score (-2init/0hard/-2soft), selected move count (45), picked move ([6.3 {null -> MANUAL_ASSEMBLY}, 6.3 {null -> a.0}]).
2022-02-09 14:20:05,530 DEBUG [org.opt.cor.imp.con.DefaultConstructionHeuristicPhase] (pool-9-thread-1)     CH step (14), time spent (502), score (-1hard/-2soft), selected move count (46), picked move ([3.b {null -> MANUAL_ASSEMBLY}, 3.b {null -> Inve.0/0-0}]).
2022-02-09 14:20:05,532 INFO  [org.opt.cor.imp.con.DefaultConstructionHeuristicPhase] (pool-9-thread-1) Construction Heuristic phase (0) ended: time spent (504), best score (-1hard/-2soft), score calculation speed (1446/sec), step total (15).
2022-02-09 14:20:05,641 DEBUG [org.opt.cor.imp.loc.DefaultLocalSearchPhase] (pool-9-thread-1)     LS step (0), time spent (613), score (0hard/-2soft), new best score (0hard/-2soft), accepted/selected move count (100/100), picked move ([a.0..6.3] {f.4} <-reversing-> [8.2..f.2] {a.4}).
2022-02-09 14:20:05,642 INFO  [org.opt.cor.imp.loc.DefaultLocalSearchPhase] (pool-9-thread-1) Local Search phase (1) ended: time spent (614), best score (0hard/-2soft), score calculation speed (1010/sec), step total (1).
2022-02-09 14:20:05,644 INFO  [org.opt.cor.imp.sol.DefaultSolver] (pool-9-thread-1) Solving ended: time spent (614), best score (0hard/-2soft), score calculation speed (1120/sec), phase total (2), environment mode (REPRODUCIBLE), move thread count (NONE).
Explanation of score (-1hard/-2soft):

From the log, it says "Construction Heuristic phase (0) ended: time spent (504), best score (-1hard/-2soft)" but why LOCAL SEARCH remembers the best score as "new best score (0hard/-2soft)" and then stopped, but reporting finalbestsolution with "Explanation of score (-1hard/-2soft)"?

Answer 1

I figured out what went wrong.

Radovan is correct that optaplanner will use the score after all planning variable is initialized.

But my problem is I see the solution score in the planning solution is different from the score I get by using scoreManager. Causing the confusion.

What caused this is that I used to have the planning entity, and my constraints (written in constraints stream) all use the planning entity as initial match statement (".from(...)"), but later on in my domain model, I decided to change the planning entity to another class, and keep the class as the anchor of the new planning entity. And I still kept all the old constraints which match using the old class which is no longer the planning entity, because I thought its the anchor so I can trace to all the other planning entities. Basically I thought I could get away from not having to rewrite the constraints after changing the planning entity to another class.

That caused many unexplainable problem, one of it is the score in the solution is different from that reported by scoreManager.

I found this problem through this link:

OptaPlanner Solution's score not matches the score given by `ScoreManager::explainScore`

After I set FULL_ASSERT on, I immediately see optaplanner report error on the constraints. So I took the time to rewrite the constraints and now the problem is gone.

Answer 2

The score is feasible only if the hard score is >= 0 and the solution has been fully initialized. For example, a solution represented by the score (-2init/0hard/-2soft) is NOT feasible, as there are two planning entities that have not been initialized yet.

According to the log you provided, the construction heuristic initialized the solution with a score (-1hard/-2soft). Then, the local search improved the solution further to the score (0hard/-2soft) and the solver terminated as the termination condition was met.

As for the "Explanation of score" in the log; I don't think it comes from the solver run itself. Are you by any chance using ScoreManager to explain the solution?

Can you verify what the score is for the best solution you receive after the solver terminates?