Order of facts in ProblemFactCollectionProperty matters for Solution in Optaplanner

I have problem where I need to assign java Money values to my entities with this very basic idea in my PlanningEntity:

@ProblemFactCollectionProperty
@ValueRangeProvider(id = "amountFacts")
private Set<Money> amountFacts;

@PlanningVariable(valueRangeProviderRefs = "amountFacts")
private Money amount;

Most of the time this is working just fine, however, I’ve run into a specific problem were the planner fails to find a (possible) working solution.

The strange part: Optaplanner does find the solution if I replace the Set with a List. I’ve double checked and the facts stay the same. If I sort the List it once again fails to find the solution. So if the solution is found sometimes seems to depend on the order of the facts in the fact collection.

Increasing the timeouts to give the planner more time does not help unfortunately.

The issue you’re encountering with OptaPlanner when using a Set<Money> for your planning variable, as opposed to a List<Money>, is likely related to how the underlying algorithms process and handle the collections of planning entities. When using a Set, the order of elements is not guaranteed, which can affect how solutions are explored during the planning process. Here are several potential reasons for the discrepancy and some suggestions on how to resolve it:

Reasons for the Issue

  1. Hashing and Equality: Set uses hashing to manage its elements, and the implementation of Money (if it doesn’t have correctly implemented hashCode() and equals() methods) may lead to unpredictable behavior. If two Money objects are considered equal but have different references, the planner might not handle them as expected.
  2. Order Sensitivity: Certain algorithms in OptaPlanner might be sensitive to the order of elements when searching for solutions. Using a List allows for more flexibility in accessing and arranging elements, which can impact the search space.
  3. Domain Complexity: If your planning problem is complex, even slight differences in the order of facts can lead to different paths in the search tree, influencing the optimizer’s ability to find solutions.

Recommendations

  1. Implement hashCode() and equals(): Ensure that your Money class has properly implemented hashCode() and equals() methods. This can help avoid unexpected behavior when using a Set.
@Override
public boolean equals(Object obj) {
    if (this == obj) return true;
    if (obj == null || getClass() != obj.getClass()) return false;
    Money money = (Money) obj;
    return value.equals(money.value) && currency.equals(money.currency);
}

@Override
public int hashCode() {
    return Objects.hash(value, currency);
}
  1. Use a List with Controlled Order: If changing to a List works, you could consider keeping the List approach and managing the order explicitly, either by sorting or by maintaining the order based on your application’s requirements.
  2. Debugging and Logging: Introduce logging to analyze the collection of facts being used during different runs. Check whether the elements are being processed as expected and whether the constraints are satisfied.
  3. Review Constraints: Ensure that the constraints you have defined in your OptaPlanner configuration are appropriate and that they align with the logic of how you’re assigning Money values. Complex constraints can lead to the planner missing viable solutions.
  4. Planning Variable Configuration: If you’re using a List, consider utilizing OptaPlanner’s valueRangeProviderRefs to control how the planning variable values are selected. This may help in maintaining consistency in the order or structure of the facts used.

Example of Sorting a List

If you go with a List, you might sort it like this:

List<Money> sortedAmountFacts = new ArrayList<>(amountFacts);
Collections.sort(sortedAmountFacts, Comparator.comparing(Money::getValue)); // Adjust comparator as needed

Summary

Switching from a Set to a List seems to yield a solution, indicating that order and element access patterns significantly influence the behavior of OptaPlanner in your specific case. By ensuring your Money class is correctly implemented, thoroughly testing constraints, and potentially controlling the order of your facts, you can achieve more consistent results.