Solution May Not Be Fully Initialized

[lepsch22]

Hello all I was wondering when/why I would be getting the warning when my solver starts up that DefaultConstructionHeuristicPhase terminated early with step count (2). The solution may not be fully initialized. I’m wondering if this behavior would affect the correctness of my solution and why it may be happening. Thanks so much!

[Christopher-Chianelli]

What is your configured termination? The solver can stop the construction heuristic if its configured termination tell it to terminate before the construction heuristic is complete (for example, a 1 second termination will terminate the solver after 1 second, regardless of if the construction heuristic complete or not). If you want to wait for the CH to be finished regardless of how long it may take, combine your current termination with a bestScoreFeasible termination (https://docs.timefold.ai/timefold-solver/latest/optimization-algorithms/overview#combiningMultipleTerminations , https://docs.timefold.ai/timefold-solver/latest/optimization-algorithms/overview#bestScoreFeasibleTermination).

[crispzendisc]

For more context, we implemented a custom move factory and we are using that factory for both the heuristic and the local search phases. In our heuristic phase config, we have millisecondsSpentLimit set to 1000. Our MoveIteratorFactory effectively iterates through and returns all possible ways of assigning different entities, including the "unassigning" move (our problem allows unassigning entities). The MoveIteratorFactory prunes certain moves in special cases, but this "may not be fully initialized" problem happens even in very basic problems where the pruning logic is essentially bypassed. I think we started seeing this logic when we switched to using custom moves.

As an example, we can send in a problem with a single entity which has a single possible timeslot. The two possible outcomes of this problem are either assigning the entity to the timeslot or leaving it unassigned. In this case, we see this kind of log: DefaultConstructionHeuristicPhase terminated early with step count (21544). The solution may not be fully initialized. For larger more complex problems, the logged step count is much smaller (e.g., single digits).

Given this, it seems like our heuristic phase is cycling endlessly until the time limit is reached. Do you have any insight into why, in this simple example, the phase isn't "realizing" it has assigned the entity after a single step, accepting that step, and terminating right away?

[Christopher-Chianelli]

If I am understanding you correctly, with your configuration, the construction heuristic will only run for 1 second; it will terminate early when 1 second is up, even if the solution is not initialized. The spent limit is not for steps, it for the entire phase itself. By default, CH tries every value and pick the one with the best score; it does this even if it finds a move that does not break hard constraints. You might want to change the pick early type: https://docs.timefold.ai/timefold-solver/latest/optimization-algorithms/construction-heuristics#constructionHeuristicsPickEarlyType. Do note "First Fit" with the default pick early type is more like "Best Fit".

[crispzendisc]

Thanks for the prompt response. When you say "CH tries every value and picks the one with the best score", why would our solver not pick the "assigning" move in the simple example above, rather than taking 21544 steps before hitting the 1s limit (assigning the activity has the better score)?

We'll try adding a pick early type to see how that changes the behavior.

[Christopher-Chianelli]

Since your problem allows unassigned values, it might be the case that not assigning the value leads to a better score (in which case, it will leave the value unassigned). But since the CH terminated permaturly due to the configured spent limit, it may have simply not tried any values for that entity yet (and thus left it unassigned, since it could not try any values for that entity within the given time limit).