How to escape local optima in school timetable problem?

[plplmax]

Hi, I'm solving a school timetable problem with 1220 lessons, 40 timeslots and 15 constraints.

Problem is the Tabu Search getting stuck at ~ -200 hard.

I tried:

• strategic oscillation + tabu search
• add pillarSwapMove and pillarChangeMove
• add DifferentSubjectsSwapMoveFilter that discards useless moves
• different entityTabuRatio (0.1-0.4)
• different acceptedCountLimit (500, 1000, 2000)
• fix possible score traps in constraints
• add FairSelectorProbabilityWeightFactory (calculation speed increased from 2k to 10-13k)
• add soft constraints to guide local search algorithm
• disable subPillarType for pillarSwap and pillarChange
• Late Acceptance (worse than Tabu in my case)
• run more than 5 minutes

Hard constraints:

• Room capacity
• Teacher conflict
• Group conflict
• No gaps at first timeslot each day
• Remove redundant gaps between groups' lessons
• Subgroups from the same groups should be placed together (English group1 and English group2, etc.)
• Disallowed subjects timeslots
• Paired subjects (English and French should be sequential at least once, etc.)
• Min days between lessons with the same subject [hard]
• Some subjects must be once at first or last timeslot in a week
• Subjects distribution over week

Soft constraints:

• Day complexity distribution over week (each subject has a complexity weight)
• Min days between lessons with the same subject [soft]
• Student group subject variety (prevent sequential math, etc.)
• Teacher time efficiency (minimize gaps between lessons)
• Fair lessons distribution over week

Can you help me to figure out what I might be missing?

[Christopher-Chianelli]

It hard to say exactly, since it could be many things:

• A score trap
• The input problem has no feasible solutions
• There a bug in your constraints; use ConstraintVerifier to verify your constraints behave as expected

I suspect it a bug in your hard constraints, causing it to penalize too much. What does SolutionManager say about the infeasible solution with -200hard? Are all the hard constraint matches correct?

[plplmax]

Hard constraints penalize exactly as needed.
Solver configuration, constraints, weights: https://gist.github.com/plplmax/b018a8eabed89a1fbd4fd9d9a8fec1e6

Explanation of score (-200hard/-2814soft):

Constraint matches:
    -67hard: constraint (Subgroup time efficiency) has 36 matches:
        ...
    -28hard: constraint (Once first or last timeslot) has 28 matches:
        ...
    -26hard: constraint (Paired subjects) has 26 matches:
        ...
    -25hard: constraint (Room capacity) has 25 matches:
        ...
    -11hard: constraint (Subject variety per day) has 11 matches:
        ...
    -10hard: constraint (Group time efficiency) has 10 matches:
        ...
    -10hard: constraint (Teacher conflict) has 10 matches:
        ...
    -8hard: constraint (Subgroup conflict) has 8 matches:
        ...
    -7hard: constraint (Division conflict) has 7 matches:
        ...
    -5hard: constraint (Disallowed subjects timeslots) has 5 matches:
        ...
    -2hard: constraint (No gaps at first timeslot each day) has 2 matches:
        ...
    -1hard: constraint (Min days between lessons [hard]) has 1 matches:
        ...
    -3477soft: constraint (Day complexity) has 29 matches:
        ...
    -58soft: constraint (Min days between lessons [soft]) has 187 matches:
        ...
    -7soft: constraint (Subject sequential variety) has 7 matches:
        ...
    0: constraint (Evenly distributed lessons per day) has 0 matches:
    728soft: constraint (Teacher time efficiency) has 728 matches:
        ...

[plplmax]

Moving evenlyDistributedLessonsPerDay in medium score level:

Explanation of score (-176hard/-4medium/-3506soft):

Constraint matches:
    -57hard: constraint (Subgroup time efficiency) has 34 matches:
        ...
    -27hard: constraint (Paired subjects) has 27 matches:
        ...
    -21hard: constraint (Once first or last timeslot) has 21 matches:
        ...
    -21hard: constraint (Room capacity) has 21 matches:
        ...
    -11hard: constraint (Subject variety per day) has 11 matches:
        ...
    -10hard: constraint (Group time efficiency) has 10 matches:
        ...
    -9hard: constraint (Teacher conflict) has 9 matches:
        ...
    -8hard: constraint (Subgroup conflict) has 8 matches:
        ...
    -6hard: constraint (Division conflict) has 6 matches:
        ...
    -4hard: constraint (Disallowed subjects timeslots) has 4 matches:
        ...
    -1hard: constraint (Min days between lessons [hard]) has 1 matches:
        ...
    -1hard: constraint (No gaps at first timeslot each day) has 1 matches:
        ...
    -4medium: constraint (Evenly distributed lessons per day) has 2 matches:
        ...
    -4174soft: constraint (Day complexity) has 29 matches:
        ...
    -59soft: constraint (Min days between lessons [soft]) has 186 matches:
        ...
    -8soft: constraint (Subject sequential variety) has 8 matches:
        ...
    735soft: constraint (Teacher time efficiency) has 735 matches:
        ...