Constraint to share NO member of a list?

[hotungkhanh]

Hi,

We are trying to use Timefold to solve a Timetabling problem.

Currently, we have the 2 classes, Unit and Student. Unit is a @PlanningEntity.

Each unit has a list of students, and each student has a list of units.

We are trying to write a constraint, so that no 2 Units that have the same student can overlap.

However, we can't seem to find a method to compare 2 lists to see if they share a member.

Can anyone please help us with this?

Thank you so much!

[triceo]

Think about the problem differently. When you have lists, you immediately loose incrementality, and therefore performance.

Write your constraint in a way that it counts the number of units per student. If the number is more than 1, penalize.

[triceo]

That's exactly what I mean. For each student, you should count how many units overlap. So you would start from a student, join with a unit that matches that student, join with another unit that matches that student while overlapping with the first unit, and then group them, getting the count of such overlapping units.

There are no lists in this case. And it is fully incremental, because every time a unit changes, only the matches for that unit will be recalculated. This gives you performance and scalability.

[Christopher-Chianelli]

As to how to find units with overlapping students, you could precompute them. For example:

@PlanningSolution
public class Timetable {
    @ProblemFactCollectionProperty
    List<Unit> units;
    // ...
   
    public record ConflictingUnit(Unit unit, Unit conflictingUnit) {}
    
   @ProblemFactCollectionProperty
    public List<ConflictingUnit> calculateUnitConflictList() {
        var out = new ArrayList<ConflictingUnit>();
        for (var first : units) {
            for (var second : units) {
                if (first.getId() >= second.getId()) {
                    continue;
                }
                if (!Collections.disjoint(first.getStudents(), second.getStudents())) {
                    out.add(new ConflictingUnit(first, second));
                }
            }
        }
        return out;
    }
}

Which can then be used in a constraint stream like this:

Constraint unitStudentConflict(ConstraintFactory factory) {
    factory.forEach(ConflictingUnit.class)
                .join(Unit.class, Joiners.equal(ConflictingUnit::unit, Function.identity()))
                .join(Unit.class, Joiners.equal((conflict, unit) -> conflict.conflictingUnit(), Function.identity()),
                                  Joiners.overlapping((conflict, unit) -> unit.getStart(),
                                                      (conflict, unit) -> unit.getEnd(),
                                                      Unit::getStart, Unit::getEnd))
                .penalize(HardSoftScore.ONE_HARD)
                .asConstraint("Unit student conflict");
               
}

[hotungkhanh]

Hi! Thank you so much for your help!

Your examples were really helpful!

Here's how our ConflictingUnit looks like:

public class ConflictingUnit {
    Unit unit1;

    Unit unit2;

    int numStudent;

We made a working version with Hard score:

    private Constraint hardUnitStudentConflict(ConstraintFactory constraintFactory) {
        return  constraintFactory.forEach(ConflictingUnit.class)
                .join(Unit.class, Joiners.equal(ConflictingUnit::getUnit1, Function.identity()))
                .join(Unit.class, Joiners.equal((conflictingUnit, unit1) -> conflictingUnit.getUnit2(), Function.identity()),
                        Joiners.overlapping((conflictingUnit, unit1) -> unit1.getStart(),
                                (conflictingUnit, unit1) -> unit1.getEnd(),
                                Unit::getStart, Unit::getEnd))
                .penalize(HardSoftScore.ONE_HARD)
                .asConstraint("Hard unit student conflict");

    }

We have also created a Soft score version, which is determined by the number of students that are in the same ConflictingUnit:

    private Constraint softUnitStudentConflict(ConstraintFactory constraintFactory) {
        return  constraintFactory.forEach(ConflictingUnit.class)
                .join(Unit.class, Joiners.equal(ConflictingUnit::getUnit1, Function.identity()))
                .join(Unit.class, Joiners.equal((conflictingUnit, unit1) -> conflictingUnit.getUnit2(), Function.identity()),
                        Joiners.overlapping((conflictingUnit, unit1) -> unit1.getStart(),
                                (conflictingUnit, unit1) -> unit1.getEnd(),
                                Unit::getStart, Unit::getEnd))
                .penalize(HardSoftScore.ofSoft(1), (conflictingUnit, unit1, unit2) -> conflictingUnit.getNumStudent())
                .asConstraint("Soft unit student conflict");

    }

I am not sure what the difference between penalize() and penalizeLong() is. Can you help us distinguish the two?

Thank you so much!

[Christopher-Chianelli]

penalize and penalizeLong are essentially the same function, except penalizeLong can handle 64-bit (long) values, for use with long score variants like HardSoftLongScore. Normal scores are 32-bit (int) values. Use penalize if you are not using a long score variant.

[hotungkhanh]

As to how to find units with overlapping students, you could precompute them. For example:

@PlanningSolution
public class Timetable {
    @ProblemFactCollectionProperty
    List<Unit> units;
    // ...
   
    public record ConflictingUnit(Unit unit, Unit conflictingUnit) {}
    
   @ProblemFactCollectionProperty
    public List<ConflictingUnit> calculateUnitConflictList() {
        var out = new ArrayList<ConflictingUnit>();
        for (var first : units) {
            for (var second : units) {
                if (first.getId() >= second.getId()) {
                    continue;
                }
                if (!Collections.disjoint(first.getStudents(), second.getStudents())) {
                    out.add(new ConflictingUnit(first, second));
                }
            }
        }
        return out;
    }
}

Which can then be used in a constraint stream like this:

Constraint unitStudentConflict(ConstraintFactory factory) {
    factory.forEach(ConflictingUnit.class)
                .join(Unit.class, Joiners.equal(ConflictingUnit::unit, Function.identity()))
                .join(Unit.class, Joiners.equal((conflict, unit) -> conflict.conflictingUnit(), Function.identity()),
                                  Joiners.overlapping((conflict, unit) -> unit.getStart(),
                                                      (conflict, unit) -> unit.getEnd(),
                                                      Unit::getStart, Unit::getEnd))
                .penalize(HardSoftScore.ONE_HARD)
                .asConstraint("Unit student conflict");
               
}

Hi! We have been using this implementation for our constraint.
However, when we're writing a unit test to test the constraint, it's not working. I believe it's because we're instantiating ConflictingUnit as a Cached problem fact (@ProblemFactCollectionProperty), and so they're not created when the tests are run. (It's working fine when we're actually using the program and not testing)

Do you have a solution to this issue?

Thank you so much!