Domain model for a variation of the exam scheduling problem

[jmuletpol]

Hi,
I am currently trying to model a variation of the exam scheduling problem.
In this case, an Exam of a given Topic is performed in several Centers, every Center has 1 or more Rooms.
I want to ensure the constraint that all Exams of a given Topic are scheduled exactly to the same timeslot. For this reason, I introduced in the UML diagram a planning entity Exam that has associated several ExamInCenter (which also becomes a planning entity). In this way, the timeslot is only assigned to the Exam and, on the other hand, the Room is only assigned to the ExamInCenter.
I would like to know whether the TimeFold solver supports such a situation, where a planning entity has associated a collection of planning entities. If not, how can I design the system to enforce the restriction "Same timesolt for all exams in centers" by domain model instead of by HardConstraint?

Thank you very much in advance,
Josep

[ge0ffrey]

This old example might be related: https://github.com/TimefoldAI/timefold-solver/tree/main/examples/src/main/java/ai/timefold/solver/examples/examination
It uses the LeadingExam and FollowingExam (which both implement Exam) trick, to avoid having 2 unrelated planning entity classes, and instead just 1 entity class hierarchy.

[jmuletpol]

Hi, Geoffrey

Thank you for the reference. Yes. I looked at the examination example some time ago, but it first appeared to me different from my case.

Now I understand your proposal: to leverage a hierarchy of Exam classes and to use Shadow Variables to set the Period of ExamInCenter when the corresponding Exam is updated by the solver.

I will take a closer look.
Thanks,
Josep

[jmuletpol]

Hi,
I have succeeded implementing the model with 3 planning entities (1 being abstract). The solver works fine with the Default solver configuration provided.
The problem arises when I try to customize the solver with a SolverConfig.xml file.

If I try to set custom heuristics as:

<?xml version="1.0" encoding="UTF-8"?>
<solver xmlns="https://timefold.ai/xsd/solver" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
        xsi:schemaLocation="https://timefold.ai/xsd/solver https://timefold.ai/xsd/solver/solver.xsd">
    <environmentMode>FULL_ASSERT</environmentMode>
    <solutionClass>edu.uoc.examplanner.api.domain.model.TimeTable</solutionClass>
    <entityClass>edu.uoc.examplanner.api.domain.model.Exam</entityClass>
    <entityClass>edu.uoc.examplanner.api.domain.model.MasterExam</entityClass>
    <entityClass>edu.uoc.examplanner.api.domain.model.ExamInCenter</entityClass>
    <scoreDirectorFactory>
        <constraintProviderClass>edu.uoc.examplanner.api.domain.score.TimeTableConstraintProvider</constraintProviderClass>
    </scoreDirectorFactory>

    <constructionHeuristic>
        <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
    <localSearch>
        <localSearchType>TABU_SEARCH</localSearchType>
    </localSearch>
</solver>

I've got the following exception
The config (QueuedEntityPlacerConfig(null, null)) has no entityClass configured and because there are multiple in the entityClassSet ([class edu.uoc.examplanner.api.domain.model.Exam, class edu.uoc.examplanner.api.domain.model.MasterExam, class edu.uoc.examplanner.api.domain.model.ExamInCenter]), it cannot be deduced automatically....

Then, I have tried to customize, according to Optaplanner documentation, the FIRST_FIT metaheuristic to specify which entity to move.

<?xml version="1.0" encoding="UTF-8"?>
<solver xmlns="https://timefold.ai/xsd/solver" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
        xsi:schemaLocation="https://timefold.ai/xsd/solver https://timefold.ai/xsd/solver/solver.xsd">
    <environmentMode>FULL_ASSERT</environmentMode>
    <solutionClass>edu.uoc.examplanner.api.domain.model.TimeTable</solutionClass>
    <entityClass>edu.uoc.examplanner.api.domain.model.Exam</entityClass>
    <entityClass>edu.uoc.examplanner.api.domain.model.MasterExam</entityClass>
    <entityClass>edu.uoc.examplanner.api.domain.model.ExamInCenter</entityClass>
    <scoreDirectorFactory>
        <constraintProviderClass>edu.uoc.examplanner.api.domain.score.TimeTableConstraintProvider</constraintProviderClass>
    </scoreDirectorFactory>

    <constructionHeuristic>
        <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
        <queuedEntityPlacer>
            <entitySelector id="masterEntitySelector">
                <entityClass>edu.uoc.examplanner.api.domain.model.MasterExam</entityClass>
                <cacheType>PHASE</cacheType>
            </entitySelector>
            <changeMoveSelector>
                <entitySelector mimicSelectorRef="masterEntitySelector"/>
            </changeMoveSelector>
        </queuedEntityPlacer>
    </constructionHeuristic>
    <constructionHeuristic>
        <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
        <queuedEntityPlacer>
            <entitySelector id="slaveEntitySelector">
                <entityClass>edu.uoc.examplanner.api.domain.model.ExamInCenter</entityClass>
                <cacheType>PHASE</cacheType>
            </entitySelector>
            <changeMoveSelector>
                <entitySelector mimicSelectorRef="slaveEntitySelector"/>
            </changeMoveSelector>
        </queuedEntityPlacer>
    </constructionHeuristic> 
    <localSearch>
        <localSearchType>TABU_SEARCH</localSearchType>
    </localSearch>
</solver>

And now, an exception appears saying that the FIRST_FIT must not be configured:

The constructionHeuristicType (FIRST_FIT_DECREASING) must not be configured if the entityPlacerConfig (QueuedEntityPlacerConfig(EntitySelectorConfig(class edu.uoc.examplanner.api.domain.model.MasterExam), [ChangeMoveSelectorConfig(EntitySelectorConfig(null), null)])) is explicitly configured.] with root cause

Could you tell me what I am doing wrong?
Thank you.

[triceo]

You're likely doing nothing wrong. You're simply running into limitations of the framework - once you start deeply tweaking the solver mechanics like you do here, you are at a risk of running into a combination of settings that's not supported. For these cases, we try to produce error messages which make it clear - in this case, the message is telling you that what you're trying to do is not allowed.

Unfortunately, I don't have other advice for you than to not use FIRST_FIT_DECREASING. Eventually you may find out that for your heavily customized use case, writing a tailored custom initialization phase will work out best.

[jmuletpol]

Hi @triceo ,
Thank you for your fast answer.

Could you give me some guidelines of how to write a tailored custom initialization phase ?
And, by the way, which algorithms is the solver using if no custom configuration is used? I mean, in the DefaultConstructionHeuristicPhase and DefaultLocalSearchPhase classes?

[jmuletpol]

Hi,

Could anyone tell me if the following code is the right starting point to write a custom construction heuristic?

@Log4j2
public class CustomConstructionPhase implements CustomPhaseCommand<TimeTable> {
    @Override
    public void changeWorkingSolution(ScoreDirector<TimeTable> scoreDirector) {
        log.info("Starting custom construction heuristic");
        TimeTable timeTable = scoreDirector.getWorkingSolution();
        // Simply assign randomly the timeslots to the master exams
        timeTable.getMasterExams().forEach(masterExam -> {
            scoreDirector.beforeVariableChanged(masterExam, "timeslot");
            Timeslot ts = timeTable.getTimeslots().get((int) (Math.random() * timeTable.getTimeslots().size()));
            masterExam.setTimeslot(ts);
            scoreDirector.afterVariableChanged(masterExam, "timeslot");
            scoreDirector.triggerVariableListeners();
            ((InnerScoreDirector<TimeTable, HardSoftScore>) scoreDirector).calculateScore();
            log.info("Move: " + masterExam.getTopic().getName() + " to " + ts + ": " + timeTable.getScore());
        });
        log.info("Ending custom construction heuristic");
    }
}

In its current form, I have simply assigned random periods to exams, but this has to be improved by using problem heuristics.