Working with solutionTabuSize

[Momo Fujii]

I have a problem with the Tabu search. My solving problem is quite restrained, as most probably only one entity is movable, thus the number of steps is very limited.
By defining
       <acceptor>
          <solutionTabuSize>1000</solutionTabuSize>
       </acceptor>
in the configuration file, I expect the Tabu search to only visit each solution once, but for some reason, this is not happening, as the algorithm bounces between solutions.

2015-09-06 13:17:20,612 [main] DEBUG     LS step (0), time spent (256), score (-1hard/0medium/-1584soft), new best score (-1hard/0medium/-1584soft), accepted/selected move count (4/4), picked move (com.tiftapp.solver.domain.shift.ShiftAssignment@7003b6ac => com.tiftapp.solver.domain.employee.Employee@1af05b03).
2015-09-06 13:17:20,634 [main] DEBUG     LS step (1), time spent (278), score (-1hard/0medium/-2202soft),     best score (-1hard/0medium/-1584soft), accepted/selected move count (4/4), picked move (com.tiftapp.solver.domain.shift.ShiftAssignment@7003b6ac => com.tiftapp.solver.domain.employee.Employee@437e951d).
2015-09-06 13:17:20,641 [main] DEBUG     LS step (2), time spent (285), score (-1hard/0medium/-1584soft),     best score (-1hard/0medium/-1584soft), accepted/selected move count (4/4), picked move (com.tiftapp.solver.domain.shift.ShiftAssignment@7003b6ac => com.tiftapp.solver.domain.employee.Employee@1af05b03).
2015-09-06 13:17:20,656 [main] DEBUG     LS step (3), time spent (300), score (-1hard/0medium/-2202soft),     best score (-1hard/0medium/-1584soft), accepted/selected move count (4/4), picked move (com.tiftapp.solver.domain.shift.ShiftAssignment@7003b6ac => com.tiftapp.solver.domain.employee.Employee@437e951d).
2015-09-06 13:17:20,664 [main] DEBUG     LS step (4), time spent (308), score (-1hard/0medium/-1584soft),     best score (-1hard/0medium/-1584soft), accepted/selected move count (4/4), picked move (com.tiftapp.solver.domain.shift.ShiftAssignment@7003b6ac => com.tiftapp.solver.domain.employee.Employee@1af05b03).
2015-09-06 13:17:20,676 [main] DEBUG     LS step (5), time spent (320), score (-1hard/0medium/-2202soft),     best score (-1hard/0medium/-1584soft), accepted/selected move count (4/4), picked move (com.tiftapp.solver.domain.shift.ShiftAssignment@7003b6ac => com.tiftapp.solver.domain.employee.Employee@437e951d).
2015-09-06 13:17:20,682 [main] DEBUG     LS step (6), time spent (325), score (-1hard/0medium/-1584soft),     best score (-1hard/0medium/-1584soft), accepted/selected move count (4/4), picked move (com.tiftapp.solver.domain.shift.ShiftAssignment@7003b6ac => com.tiftapp.solver.domain.employee.Employee@1af05b03).
2015-09-06 13:17:20,688 [main] DEBUG     LS step (7), time spent (332), score (-1hard/0medium/-2202soft),     best score (-1hard/0medium/-1584soft), accepted/selected move count (4/4), picked move (com.tiftapp.solver.domain.shift.ShiftAssignment@7003b6ac => com.tiftapp.solver.domain.employee.Employee@437e951d).
2015-09-06 13:17:20,698 [main] DEBUG     LS step (8), time spent (342), score (-1hard/0medium/-1584soft),     best score (-1hard/0medium/-1584soft), accepted/selected move count (4/4), picked move (com.tiftapp.solver.domain.shift.ShiftAssignment@7003b6ac => com.tiftapp.solver.domain.employee.Employee@1af05b03).
2015-09-06 13:17:20,716 [main] DEBUG     LS step (9), time spent (360), score (-1hard/0medium/-2202soft),     best score (-1hard/0medium/-1584soft), accepted/selected move count (4/4), picked move (com.tiftapp.solver.domain.shift.ShiftAssignment@7003b6ac => com.tiftapp.solver.domain.employee.Employee@437e951d).
2015-09-06 13:17:20,724 [main] DEBUG     LS step (10), time spent (367), score (-1hard/0medium/-1584soft),     best score (-1hard/0medium/-1584soft), accepted/selected move count (4/4), picked move (com.tiftapp.solver.domain.shift.ShiftAssignment@7003b6ac => com.tiftapp.solver.domain.employee.Employee@1af05b03).

As stated in the documentation, the solution class has equals and hashCode properly implemented.

[Geoffrey De Smet]

2 possible reasons:

- If no moves are accepted, it takes the best non-accepted move. But that's probably not it.

- A 1000 solutions isn't much. That's 3 entities with 10 values, as those have a search space of 3^10.
Your dataset probably has a search space much bigger than 1000.
The log doesn't print the entire solution, only the taken move. It's not because the same move is taken, than the solution is the same (it's definitely not like that). If you want to tabu the move, use moveTabu.

PS: solutionTabu is mostly useless for non-toy problems as stated in the docs.

With kind regards,
Geoffrey De Smet

--
You received this message because you are subscribed to the Google Groups "OptaPlanner development" group.
To unsubscribe from this group and stop receiving emails from it, send an email to optaplanner-d...@googlegroups.com.
To post to this group, send email to optapla...@googlegroups.com.
Visit this group at http://groups.google.com/group/optaplanner-dev.
For more options, visit https://groups.google.com/d/optout.

[Geoffrey De Smet]

- If no moves are accepted, it takes the best non-accepted move. But that's probably not it.

This is not the case as the log clearly says there are 4 moves accepted each time.

With kind regards,
Geoffrey De Smet

[Momo Fujii]

Thanks for your answer.
In my case I ahve constructed a test-problem, which is extremly limited.
The case is the following. In a nurse rostering scenario, I have a medium constraint, which allows shifts to be free, if no suitable employee is found.

Afterwards I want to check, which hard constraint would have been active and doesn't allow this shift to be assigned proberly.
Thus I set all shifts with employee to immovable and start a second solver with a different configuration. I also switch the medium score rule to another rule, which assign -integerr infinity as a penalty for non-assigned shifts, thus forcing, despite nullable entities, all shifts to be assigned. In this case, given one shift is unassignable, this is the only planning entity, the solver can touch, and in principle only assign each of the employees once and choose the one, where I have the minimum penalty level.

I am aware, that this is more than dirty.
Is there any way to avoid a "Bailing out of neverEnding selector" in this special use case?
If in theory more than one shift can not be assigned, the number of possible solutions would grow, though.

At the moment I work with a configuration like this:

    <localSearch>
      <acceptor>
        <solutionTabuSize>1000</solutionTabuSize>
        <moveTabuSize>1000</moveTabuSize>
        <entityTabuSize>1000</entityTabuSize>
      </acceptor>
      <termination>
        <terminationCompositionStyle>OR</terminationCompositionStyle>
        <unimprovedSecondsSpentLimit>1</unimprovedSecondsSpentLimit>
        <unimprovedStepCountLimit>1</unimprovedStepCountLimit>
      </termination>
      <forager>
        <acceptedCountLimit>1000</acceptedCountLimit>
      </forager>
    </localSearch>

As far as I understant my configuration, the algorithm should stop once it tested all the possible moves.

[Momo Fujii]

Addition, <unimprovedStepCountLimit>1</unimprovedStepCountLimit> seems to get violated in this configuration, though, as there are more than 1 LS steps, if I change the unimproved seconds time limit...

[Julio Bellón]

Hello nice to meet you: 

Please, can you send me the code of that constraint rule? you said "I have a medium constraint, which allows shifts to be free, if no suitable employee is found."