I have an overconstrained problem with four planning variables on one planning entity, making them all nullable. If even one of these variables is null, the entity is regarded as not used in the solution. The construction heuristic (CH) phase runs too slowly with the default Cartesian product approach, so I am trying to optimize it. The variables are:
All four planning variables must be set for the entity to be evaluated. To enforce this, any uninitialized entity is penalized. This is the only constraint so far, and it works fine with the default slow CH.
I have tried various alternative construction heuristics, starting with picking the variables in sequence, then from a queue, and then picking the first two as Cartesian and the rest sequentially. However, in every case, individual moves do not fill in all four planning variables during scoring. As a result, the entity does not get fully initialized in any one move, the score does not improve, and it defaults to picking the first move it tried, which often includes a {null->null} assignment, leading to an uninitialized problem.
I am looking for a way to force it to pick a non-null value, given that it is nullable due to being overconstrained. I tried using <ignoreEmptyChildIterators>true</ignoreEmptyChildIterators>, but it did not have the needed effect.
Alternatively, I see three possible solutions:
1. Set resourceA, resourceB, and resourceC to non-null values: This forces the selection of a value, leaving timeslot nullable. This approach ensures that the entity can be removed from the solution while forcing a resource selection, making it scorable once a timeslot is attempted by the CH.
2. Score an entity before it is fully initialized: Once a timeslot and any one resource (A, B, or C) are set, the CH could know whether it is better or worse after a move with just two variables. This would allow picking a non-null combination, but it would conflict with the mechanism that penalizes non-fully initialized entities.
3. Use dummy variable values instead of nullable variables: This approach models the overconstrained problem with a dummy variable value that signifies the entity is not used in the solution, which is similar to a not fully initialized entity.
4. Use another way of motivating the solver to initialized entities and keep them in the solution: Maybe there is another principle to force all entity to be initalized, rather that penalizing non-initalized entities, ?
;)
The default construction heuristics are there for the most common use cases, to get people started quickly and without having to write too much custom code. However, as the uniqueness of the problem at hand grows, the limits of generic approaches become very obvious.
At a certain point, it may just be easier to write a domain-specific construction heuristic from scratch. Look into custom phases, which allow you to initialize your solution in literally any way you need - if you can express it in code, custom phase will do it.
Problems with 4 variables I think certainly fall into the category where custom phases could be beneficial. And right after that, you are likely to run into similar issues with generic moves in local search, which will in turn force you to write some custom moves.