Constraints between subsets of entities

[SuperMarcomen]

Hi,

I'm part of a team currently developing a web app to automatically generate timetables for schools as a university project. Since the requirements of schools can be quite specific, we thought of including a domain-specific language so that each school can personalize their solver with a simple scripting language.

I wanted to ask if it's possible to define constraints between two specific instances of the domain entities. For example, I want to tell the solver that "Teacher X wants to be free on Monday afternoon" instead of something like "All teachers want to be free on Monday afternoon". Currently there is the possibility to use forEach from the ConstraintFactory and then filter for one specific teacher, but is there a way of doing this more efficiently?

[triceo]

Hey there @SuperMarcomen,

typically what you'd do is you'd create a TeacherDayOffRequest problem fact and make it a part of your @PlanningSolution using @ProblemFactCollectionProperty - "Teacher X on Monday" is one instance of such a fact type, which could be a simple Java record:

record TeacherDayOffRequest(Teacher teacher, MonthDay day) {
}

(Assuming Teacher is not a planning entity. If it is, it will be better to make TeacherDayOffRequest a class, as it'll have to be cloned by the solver, and records are not cloned.)

Then you write a constraint for this fact type.

forEach(TeacherDayOffRequest.class)
    .join(Teacher.class,
        equal(TeacherDayOffRequest::teacher, Function.identity())
    ...

Out of curiosity... would you mind sharing which university do you attend?

[SuperMarcomen]

We study at the Karlsruhe Institute of technology (in Germany). Thank you for the fast response!

This helps to minimize the number of instances to be checked for the constraints we define. However, our users should also be able to define constraints themselves via the domain-specific language (DSL) and then instantiate them. To do so, we would have to be able to dynamically create new ProblemFact types during runtime, which would then also have to be checked according to the definition by the user in the DSL. An alternative we thought of would be a generic ProblemFact which injects the definition and instance of the constraint into a generic constraint that would check all ProblemFacts according to the definition given in the ProblemFact. For this we would need to know if it is possible to define a constraint during runtime (including the ability to define for each instance, whether it is going to be penalized or rewarded and whether it is a soft or hard constraint).

[triceo]

The question of a DSL for constraints seems unrelated to the solver - you can have any DSL you prefer, as long as you can translate it into the constraints understood by the solver. Therefore I'm going to leave the DSL aside.

The question of user-defined constraints is a different matter. Although I can imagine writing a completely generic constraint which can penalize anything based on anything else, I want to discourage you from going down that route - you will run into issues with constraint weights. If the users can define literally any constraint, they also need to have the power of deciding the weights of these constraints, and balancing them against each other.

Balancing constraints is a tricky problem, as doing it wrong introduces score traps, reducing the effectiveness of the solver. This is the sort of power with which comes a great responsibility, and I would not give it in the hands of untrained users. Arguably, providing such training and appropriate user interfaces is outside the scope of any university project; but I won't be the judge of that. My recommendation though is to select a subset of things you allow people to override, write the constraints for that specifically, and take care of the balancing yourself. Too much flexibility can sometimes be a bad thing, and in this particular case, it opens a can of worms you may not be ready to open.

When it comes to tweaking constraint weights dynamically, Constraint Configuration is your friend.