Starting from the following configuration in configSolver.xml.
If I want to override this configuration by adding a filter selection class for the ChangeMove and SwapMove classes (AFAIK, a union of those 2 moves is used by default in the Local Search Phase, and a Cartesian product with ChangeMove for each planning value is used in the Construction Heuristics Phase) in this configSolver.xml, how should I proceed?
Should I have to reproduce the default config for those 2 phases, then overwrite it with the selection filter applied, or is there a better approach? I tried to do the following (at the moment it seems that it works properly, but I don't know if this is best practice):
<!-- Construction Heuristics generic config -->
<constructionHeuristic>
<constructionHeuristicType>ALLOCATE_ENTITY_FROM_QUEUE</constructionHeuristicType>
<entitySorterManner>DECREASING_DIFFICULTY_IF_AVAILABLE</entitySorterManner>
<valueSorterManner>DECREASING_STRENGTH_IF_AVAILABLE</valueSorterManner>
<cartesianProductMoveSelector>
<changeMoveSelector>
<!-- Apply the filter only for Timeslot planning value -->
<filterClass>com.patrick.timetableappbackend.utils.LessonChangeMoveFilter</filterClass>
<valueSelector variableName="timeslot"/>
</changeMoveSelector>
<changeMoveSelector>
<valueSelector variableName="room"/>
</changeMoveSelector>
</cartesianProductMoveSelector>
</constructionHeuristic>
<!-- Late_Acceptance configuration-->
<localSearch>
<!-- Termination configuration -->
<unionMoveSelector>
<changeMoveSelector>
<filterClass>com.patrick.timetableappbackend.utils.LessonChangeMoveFilter</filterClass>
</changeMoveSelector>
<swapMoveSelector>
<filterClass>com.patrick.timetableappbackend.utils.LessonSwapMoveFilter</filterClass>
</swapMoveSelector>
</unionMoveSelector>
<!-- Acceptor and forager -->
</localSearch>
<!-- Tabu_Search configuration-->
<localSearch>
<unionMoveSelector>
<changeMoveSelector>
<filterClass>com.patrick.timetableappbackend.utils.LessonChangeMoveFilter</filterClass>
</changeMoveSelector>
<swapMoveSelector>
<filterClass>com.patrick.timetableappbackend.utils.LessonSwapMoveFilter</filterClass>
</swapMoveSelector>
</unionMoveSelector>
<!-- Acceptor and forager -->
</localSearch>
Note that I have implemented the filters (for both ChangeMove and SwapMove) separately in a similar way to the examples from the documentation.
ChangeMove:
package com.patrick.timetableappbackend.utils;
import ai.timefold.solver.core.api.score.director.ScoreDirector;
import ai.timefold.solver.core.impl.heuristic.selector.common.decorator.SelectionFilter;
import ai.timefold.solver.core.impl.heuristic.selector.move.generic.ChangeMove;
import com.patrick.timetableappbackend.model.Lesson;
import com.patrick.timetableappbackend.model.Timeslot;
import com.patrick.timetableappbackend.model.Timetable;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import java.time.Duration;
public class LessonChangeMoveFilter implements SelectionFilter<Timetable, ChangeMove> {
private static final Logger LOGGER = LoggerFactory.getLogger(LessonChangeMoveFilter.class);
@Override
public boolean accept(ScoreDirector<Timetable> scoreDirector, ChangeMove changeMove) {
Lesson lesson = (Lesson) changeMove.getEntity();
Object planningValue = changeMove.getToPlanningValue();
// Ensure the value is of type Timeslot
if (!(planningValue instanceof Timeslot)) {
return true; // Accept the move if the target value is not a Timeslot
}
Timeslot toTimeslot = (Timeslot) planningValue;
return isMatching(lesson, toTimeslot);
}
private int calculateTimeslotDuration(Timeslot timeslot) {
Duration duration = Duration.between(timeslot.getStartTime(), timeslot.getEndTime());
return (int) duration.abs().toHours();
}
private boolean isMatching(Lesson lesson, Timeslot timeslot) {
int timeslotDuration = calculateTimeslotDuration(timeslot);
return (timeslotDuration == lesson.getDuration());
}
}
SwapMove:
package com.patrick.timetableappbackend.utils;
import ai.timefold.solver.core.api.score.director.ScoreDirector;
import ai.timefold.solver.core.impl.heuristic.selector.common.decorator.SelectionFilter;
import ai.timefold.solver.core.impl.heuristic.selector.move.generic.SwapMove;
import com.patrick.timetableappbackend.model.Lesson;
import com.patrick.timetableappbackend.model.Timeslot;
import com.patrick.timetableappbackend.model.Timetable;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import java.time.Duration;
public class LessonSwapMoveFilter implements SelectionFilter<Timetable, SwapMove> {
private static final Logger LOGGER = LoggerFactory.getLogger(LessonSwapMoveFilter.class);
@Override
public boolean accept(ScoreDirector<Timetable> scoreDirector, SwapMove swapMove) {
Lesson leftLesson = (Lesson) swapMove.getLeftEntity();
Lesson rightLesson = (Lesson) swapMove.getRightEntity();
return isMatching(leftLesson, rightLesson);
}
private int calculateTimeslotDuration(Timeslot timeslot) {
Duration duration = Duration.between(timeslot.getStartTime(), timeslot.getEndTime());
return (int) duration.abs().toHours();
}
private boolean isMatching(Lesson lessonA, Lesson lessonB) {
int timeslotDurationA = calculateTimeslotDuration(lessonA.getTimeslot());
int timeslotDurationB = calculateTimeslotDuration(lessonB.getTimeslot());
return (timeslotDurationA == lessonA.getDuration()) && (timeslotDurationB == lessonB.getDuration());
}
}
EDIT: It seems that the above solution works pretty well, but I don't know if this is best practice to override the default configuration of Construction Heuristics and Local Search phases with Selection Filter since the quality of the scheduling problem's solution is slightly poorer than the default configuration with no Selection Filter.
Environment
If I understand your filter correctly, you are making a filter so Lessons only get Timeslots of the correct length. This is a good use case for ValueRangeProvider on the Planning Entity. To do this:
Remove the ValueRangeProvider annotation for Timeslot from the PlanningSolution class.
Add a method annotated with ValueRangeProvider on Lesson that return the List of Timeslots that can be assigned to the Lesson:
@PlanningEntity
public class Lesson {
Timetable timetable; // Used to access possible timeslots
// ...
@ValueRangeProvider
public List<Timeslot> getPossibleTimeslots() {
return timetable.getTimeslots().stream().filter(this::matchesTimeslot).toList();
}
private boolean matchesTimeslot(Timeslot timeslot) {
var timeslotDuration = Duration.between(timeslot.getStartTime(), timeslot.getEndTime());
return (timeslotDuration.abs().toHours() == duration);
}
}
With these changes, the filter can be removed from the SolverConfig (as each Lesson gets it own independent value range).
However, as noted in the docs, by limiting the value range of each Lesson, you are effectively creating a built-in hard constraint. This can have the benefit of severely lowering the number of possible solutions; however, it can also take away the freedom of the optimization algorithms to temporarily break that constraint in order to escape from a local optimum.