Search code examples
constraintsoptaplannertimefold

Timefold Solver applies the constraints based on priority/order of constraints (from ConstraintProvider) by default?


Does Timefold Solver apply (and check) the constraints in a order (or priority) which is defined in ConstraintProvider by default? Or, to be more exactly, how does the Solver's constraints work when it tries to solve a specific problem?

Consider the following case with 2 constraints:

  • Constraint A (with a complex implementation)
  • Constraint B (with a simple implementation; i.e. simple check of a condition)

What is the order in which those 2 constraints are applied?

And there is a way to order the constraints in ConstraintProvider so that the constraints will be applied more efficiently?

For example:

Case a): The order of constraints is Constraint A, Constraint B

After applying Constraint A (and perform the necessary moves for a better solution), in Constraint B there will be chances of no penalization.

Case b): The order of constraints is Constraint B, Constraint A

After applying Constraint B (and perform the necessary moves for a better solution), in Constraint A there will be chances of additional penalizations.

I hope the questions make sense. If not, feel free to edit this post. Any help will be appreciated.


Solution

  • There is no ordering of constraints because all constraints exist in one big bucket and cannot be distinguished from one another, like liquids mixed into a homogeneous solution. All constraints are evaluated simultaneously.

    Consider the two constraint streams:

    A: forEach(Visit.class)
           .penalize(ONE_SOFT)
    B: forEach(Visit.class)
           .filter(visit -> !visit.isApplicable())
           .penalize(ONE_HARD)
    

    Notice that they share something in common:

    forEach(Visit.class)
    

    This means the solver will send all Visits through there first. (And therefore, now matter how many constraints you have, Visits will only be processed once!) From there, Visits will continue to:

    A2: penalize(ONE_SOFT)
    B2: filter(...)
    

    In A2, all the Visit instances will terminate by a penalty. In B2, however, all Visit instances which match the filter continue on:

    B3: penalize(ONE_HARD)
    

    And there, all Visit processing finally finishes.

    In other words - the constraints build a graph of nodes; the sources are forEach() nodes, and the sinks are penalties. And then the solver sends all problem facts and entities through that graph. These nodes have an order in which they will be processed, and that ordering will probably be related to the original ordering of the constraints that created those nodes, but it is largely irrelevant - if the nodes were ordered differently, the result would be exactly the same; the only thing that matters is the edges between those nodes. We start from the source nodes, and we move along the edges towards the sink nodes.

    From this, I hope you can see that there is no constraint order. All constraints are broken down and turned into a single node network, which has penalties at the end. This is pretty much what a RETE algorithm does.