Optaplanner: Meta Heuristic and Brute Force Solution do not match even if enough time is given to MH

Question

My understanding is Brute Force will always give the best solution but will not scale. While Meta Heuristic will give best possible in certain time limit. Meaning If Enough time is given, it should match with Brute Force Solution.

But, In my implementation it is not happening. I am getting best solution by Brute Force algorithm, but not the same with MH even If i give enough time. What could be the reason. I reason I could think of is MH getting stuck in Local maxima. But, I have tried to avoid that from my understanding.

I am not sharing the implementation as it is complex. If needed will share the code.

UPDATE:

My MoveSelector configuration-

<?xml version="1.0" encoding="UTF-8"?>
<solver>
  <!-- Domain model configuration -->
  <solutionClass>com.example.CutSolution</solutionClass>
  <entityClass>com.example.Size</entityClass>


  <!-- Score configuration -->
  <scoreDirectorFactory>
    <easyScoreCalculatorClass>com.example.CutplanEasyScoreCalculator</easyScoreCalculatorClass>
  </scoreDirectorFactory>

  <constructionHeuristic>
    <constructionHeuristicType>FIRST_FIT</constructionHeuristicType>
  </constructionHeuristic>
  <localSearch>
    <termination>
      <unimprovedSecondsSpentLimit>10</unimprovedSecondsSpentLimit>
    </termination>
    <unionMoveSelector>
      <changeMoveSelector/>
      <swapMoveSelector/>
      <pillarChangeMoveSelector/>
      <pillarSwapMoveSelector/>
    </unionMoveSelector>
    <acceptor>
      <entityTabuRatio>0.02</entityTabuRatio>
    </acceptor>
    <forager>
      <acceptedCountLimit>1000</acceptedCountLimit>
    </forager>
  </localSearch>
</solver>

I have only one Planning Entity and One Planning Variable.

Thanks.

Answer 1

Probably gets stuck in a local optima indeed. Adding additional move selectors to help it get unstuck is usually the best solution.

This sort of getting stuck happens more on small datasets (downscaling). Metaheuristics excel at upscaling, but - with only vanilla move selectors - it doesn't downscale well in some cases.