Exam scheduling (proprietary implementation) with tabu search always fails under the same constraints despite increasing the scoreHard value

Question

I have a similar implementation to Exam Scheduling, but the relationships are different as there are two ManyToMany, Rooms and Teachers relationships with the Exam class. I have a small example with two courses, using TabuSearch, but the execution solver always fails under the same constraint, despite there being space in other rooms and teachers. The constraint always fails on the same classes, it seems that the solution is cached despite deleting everything before solving. Has anyone ever had similar behavior?

<solver>
  <!--<moveThreadCount>AUTO</moveThreadCount>--><!-- To solve faster by saturating multiple CPU cores -->

  <!--moveThreadCount>AUTO</moveThreadCount-->

  <solutionClass>org.acme.timetabling.domain.ExameTable</solutionClass>
  <entityClass>org.acme.timetabling.domain.Exame</entityClass>
  <entityClass>org.acme.timetabling.domain.docente.Docente_Assignment</entityClass>
  <entityClass>org.acme.timetabling.domain.sala.Sala_Assignment</entityClass>

  <scoreDirectorFactory>
    <constraintProviderClass>org.acme.timetabling.solver.ExameTableConstraintProvider</constraintProviderClass>
    <initializingScoreTrend>ONLY_DOWN</initializingScoreTrend>
    <!--<scoreDrl>org/acme/timetabling/solver/ExameTableDrolls.drl</scoreDrl>-->
  </scoreDirectorFactory>

  <!--<termination>-->
    <!--<minutesSpentLimit>1</minutesSpentLimit>-->
  <!--</termination>-->
  <!-- Tabu Search performs much better than Late Acceptance (default algo) on this use case -->
<!--  <constructionHeuristic>-->
<!--    <constructionHeuristicType>FIRST_FIT</constructionHeuristicType>-->
<!--  </constructionHeuristic>-->

  <constructionHeuristic>
    <queuedEntityPlacer>
      <entitySelector id="placerEntitySelector">
        <cacheType>PHASE</cacheType>
        <entityClass>org.acme.timetabling.domain.Exame</entityClass>
      </entitySelector>
      <changeMoveSelector>
        <entitySelector mimicSelectorRef="placerEntitySelector"/>
      </changeMoveSelector>
    </queuedEntityPlacer>
  </constructionHeuristic>
  <localSearch><localSearchType>TABU_SEARCH</localSearchType></localSearch>

Have a better solution in the tabu search, because when consulting the prints it is possible to see another solution with a better score than the final solution.

Answer 1

The solver runs are perfectly reproducible - in other words, if you run the same config any number of times, you will get the same result each and every time. (Unless you specifically configured the solver not to behave like this, by setting the environmentMode.) So the fact that you always see the same solution is not surprising, or a problem - it is the expected behavior with the default configuration.

The problem you're describing sounds like you're getting stuck in local optima. Use more move types, introduce constraints to avoid score traps, let the solver run for longer.

Also, the fact that you know there is a better solution out there shows that the problem you're solving likely isn't large enough. I suggest you run the solver on a bigger problem, bigger than you can solve as a human, and stop worrying about trivial data sets.