[SOLVED] Setting a predecessor constraint in timefold python

Setting a predecessor constraint in timefold python

I am trying to implement a predecessor constraint similar to the Job Scheduling example given in java.

But I struggle with the ordering constraint definition to consider predecessors.

I have defined my time slots simply as ordered integers :

@dataclass
class Timeslot:
    slot : int

And my operations as planning entities with few boolean operations and predecessors as a list of other operations id :

@planning_entity
@dataclass
class Operation:
    id: Annotated[int, PlanningId]
    name: str
    predecessors: list[int]
    timeslot: Annotated[Timeslot, PlanningVariable] = field(default=None)

    def isPred(self,other):
        return other.id in self.predecessors

    def isAfter(self,other):
        return self.timeslot.slot < other.timeslot.slot

And then my constraint as :

def precondition_conflict(constraint_factory: ConstraintFactory) -> Constraint:
    # Respect order constraints
    return (
        constraint_factory.for_each_unique_pair(Operation)
        .filter(lambda op1, op2 : op1.isPred(op2))
        .filter(lambda op1, op2 : op1.isAfter(op2))
        .penalize(HardSoftScore.ONE_HARD)
        .as_constraint("Order conflict")
    )

Then I instanciate my problem :

 operations.append(Operation(1,"OP N°1 : Bake the cake",[3]))
 operations.append(Operation(2,"OP N°2 : Enjoy your meal",[4]))
 operations.append(Operation(3,"OP N°3 : Mix flour, eggs and whatever they say in the recipe",[]))
 operations.append(Operation(4,"OP N°4 : take it out of the oven",[1]))

But the solver keeps giving me solutions where the operations order is incorrect, with 0 hard constraint violated. For instance :

INFO:timefold.solver:Solving ended: time spent (30056), best score (0hard/0soft), move evaluation speed (219895/sec), phase total (2), environment mode (PHASE_ASSERT), move thread count (NONE).
INFO:app:+------------------+------------------+
INFO:app:|0                 |OP N°4 : take it out of the oven|
INFO:app:+------------------+------------------+
INFO:app:|1                 |OP N°2 : Enjoy your meal|
INFO:app:+------------------+------------------+
INFO:app:|2                 |OP N°3 : Mix flour, eggs and whatever they say in the recipe|
INFO:app:+------------------+------------------+
INFO:app:|3                 |OP N°1 : Bake the cake|
INFO:app:+------------------+------------------+

Where obviously I expected 3 -> 1 -> 4 -> 2

Where did I do it wrong?

SOLUTION (thanks to Lukáš Petrovický):

def precondition_conflict(constraint_factory: ConstraintFactory) -> Constraint:
    # Respect order constraints
    return (
        constraint_factory.for_each(Operation)
        .join(Operation)
        .filter(lambda op1, op2 : op1.isPred(op2))
        .filter(lambda op1, op2 : op1.isAfter(op2))
        .penalize(HardSoftScore.ONE_HARD)
        .as_constraint("Order conflict")
    )

Solution

Unique pairs are tricky. In this case, you probably want to avoid using them, and instead go for a standard join.

Consider three operations: A, B, C. Unique pairs will give you A+B, A+C and B+C. It assumes that whatever is true for A+B, it is also true for B+A and therefore processing both would be redundant. But this is not true in your case.

A standard join would fix it, enumerating all possible pairs. Or a better filter, which checks the condition from both sides.